Prime numbers

The earliest surviving study of primes is Greek. Euclid's Elements, compiled around 300 BCE, proves in Book IX, Proposition 20 that no finite list of primes can be complete: multiply the listed primes together, add one, and whatever divides the result is a prime that was not on the list. The same book proves the fundamental theorem of arithmetic and shows how to build a perfect number out of a prime of the form 2^p − 1. Greek writers called them prōtos arithmòs, the "first" numbers. The Rhind Mathematical Papyrus of about 1550 BCE does expand fractions with prime and with composite denominators, and that is sometimes offered as evidence that Egyptian scribes recognised the distinction — the papyrus never says so, and the reading is inference rather than record.

Even the sieve named after Eratosthenes reaches us at second hand. The earliest surviving description is in Nicomachus of Gerasa's Introduction to Arithmetic, written early in the second century CE, which credits Eratosthenes of Cyrene — and then describes sieving by odd numbers rather than by primes.

Progress afterwards came in bursts. Around 1000 CE Ibn al-Haytham stated the result now known as Wilson's theorem. Fibonacci's Liber Abaci of 1202 was the first book to set out trial division, including the labour-saving point that you may stop at the square root. Fermat stated his little theorem in 1640, and Marin Mersenne catalogued primes of the form 2^p − 1. In 1737 Euler proved that the sum of the reciprocals of the primes diverges, which pulled analysis into what had been pure arithmetic. Legendre and Gauss each conjectured, around 1800, that the number of primes below x approaches x/ln x; Riemann's 1859 paper on the zeta function sketched a route to a proof, and Hadamard and de la Vallée Poussin completed it independently in 1896.

Membership shifted too. Some Greek writers treated primes as a subdivision of the odd numbers and so did not count 2, and Christian Goldbach was still listing 1 as prime in his letters to Euler in the mid-eighteenth century. Euler disagreed, and the modern convention follows him.

Key properties

• 2 is the only even prime. Every prime above 3 is one less or one more than a multiple of 6, because the other four residues mod 6 are divisible by 2 or by 3.
• There are infinitely many primes — Euclid, Elements, Book IX, Proposition 20.
• Every integer above 1 is a product of primes in exactly one way apart from their order: the fundamental theorem of arithmetic.
• 1 is not prime by modern convention, because admitting it would destroy the uniqueness of that factorisation.
• There are 25 primes below 100, 168 below 1,000, 1,229 below 10,000, 78,498 below one million and 50,847,534 below one billion.
• The prime number theorem — proved in 1896 by Hadamard and de la Vallée Poussin — says the count of primes up to x is asymptotic to x/ln x.
• The sum of the reciprocals of the primes diverges (Euler, 1737), even though the primes have density zero among the integers.
• Bertrand's postulate, proved by Chebyshev in 1852, guarantees at least one prime strictly between n and 2n for every n greater than 1.

Where they turn up

• RSA and Diffie–Hellman key generation both pick large primes; RSA's security rests on the difficulty of recovering two primes from the product nobody minds publishing.
• Hash tables and checksum schemes commonly use a prime modulus, since a modulus sharing a factor with the stride of the input collapses distinct keys into the same bucket.
• Finite fields — whose sizes are always a prime or a prime power — underpin error-correcting codes, including the Reed–Solomon codes used on compact discs and in QR codes.
• The 13-year and 17-year life cycles of the Magicicada periodical cicadas are prime. That this evolved to frustrate predators with shorter cycles is a long-standing hypothesis, not a settled result.
• On 12 October 2024 the Great Internet Mersenne Prime Search found 2^136,279,841 − 1, a prime of 41,024,320 digits, on a cloud machine volunteered by Luke Durant of San Jose. It was still the largest prime known in September 2026.