Why there are infinitely many primes: Euclid's proof
Euclid's 2,300-year-old proof shows primes never run out, though 30,031 = 59 × 509 shows his 'multiply and add one' trick needn't make a prime.
Yes, there are infinitely many prime numbers, and Euclid proved it around 300 BC in Book IX of his Elements, in one of the first known proofs by contradiction. Primes are whole numbers above 1 divisible only by 1 and themselves.
The argument fits in a paragraph. Suppose you held a complete, finite list of primes. Multiply them all together and add 1. Dividing the result by any prime on your list leaves a remainder of 1, so none of them divides it. But every whole number above 1 has at least one prime factor, so some prime must be missing from the list. No finite list can ever be complete.
Many retellings claim the product plus one is itself a new prime. Often it is, but the pattern breaks quickly:
| Primes multiplied | Product + 1 | Prime? |
|---|---|---|
| 2 × 3 × 5 × 7 | 211 | Yes |
| 2 × 3 × 5 × 7 × 11 | 2,311 | Yes |
| 2 × 3 × 5 × 7 × 11 × 13 | 30,031 | No: 59 × 509 |
That doesn’t hurt the proof at all. Neither 59 nor 509 was on the list, and an unlisted prime factor is all Euclid needed.
Euclid also never wrote “infinitely many”. The Greeks had no modern notion of infinity, so he said prime numbers are more than any assigned multitude: name any finite collection, and there is a prime outside it.
Infinite does not mean common. By the prime number theorem, the chance that a number near x is prime is about 1 in ln x, so among 1,000-digit numbers only about one in 2,300 is prime.
That thinning hasn’t stopped the hunt. The largest known prime, 2^136,279,841 − 1, has 41,024,320 digits. Luke Durant found it on 12 October 2024 for the Great Internet Mersenne Prime Search, using thousands of cloud GPUs. Euclid guarantees a bigger one is out there.
Sources & references
5 referencesWell-established. Corroborated by 4 independent sources.
