Euclid's proof that there are infinitely many prime numbers

The statement

In Book IX, Proposition 20 of the Elements (c. 300 BC), Euclid states (as rendered in D. E. Joyce's online edition) that the prime numbers outnumber any finite collection of primes one cares to name. In modern words: for any finite collection of primes there is a prime not in it, so there are infinitely many primes.

The argument

1. Take any finite list of primes p1, p2, ..., pn.
2. Form N = p1 × p2 × ... × pn + 1.
3. N > 1, so N has at least one prime factor q (it may be N itself).
4. Each listed prime divides N − 1, so dividing N by any of them leaves remainder 1. Therefore q is not on the list.

Since the list was arbitrary, every finite list of primes misses at least one prime.

A common misreading

The argument does not claim that N is prime. For the first six primes, 2·3·5·7·11·13 + 1 = 30031 = 59 × 509: composite, yet both factors are new primes. Chris Caldwell's PrimePages gives a larger example with the list {2, 3, 7, 43, 13, 139, 3263443}, whose product plus one factors as 547 × 607 × 1033 × 31051.

How the proof is classified

Textbooks often present the result as a proof by contradiction ("suppose there are finitely many primes..."). The Wikipedia article on Euclid's theorem notes that this is a common mis-description of Euclid's text, which can be read as a direct argument by cases (the new number is either prime or has a new prime factor).

Limits and caveats

The proof shows that primes never run out but says nothing about how densely they occur; that is the subject of the prime number theorem. The wording of Euclid's proposition comes to us through translations, so quoted phrasings vary between editions.