Euclid's proof that the primes never end Image: Mark A. Wilson (public domain)

Euclid's proof that the primes never end

Around 300 BC, in Alexandria, Euclid wrote down a proof that the prime numbers never run out. It occupies Proposition 20 of Book IX of the Elements, it takes about ten lines, and it is still the first proof that most students of mathematics see. Its age is not the reason it is taught. It is taught because it is a perfect specimen: a statement about infinitely many objects, settled by an argument that handles only finitely many of them at a time.

What Euclid actually claimed

Euclid did not use the word infinite. His statement reads, in the standard translation, "prime numbers are more than any assigned multitude of prime numbers". That is, hand him any finite list of primes and he will produce a prime that is not on it. The modern statement, that the set of primes is infinite, is the same thing said in a vocabulary that did not exist in his time.

His proof is for three primes, which was the Greek way of writing a proof for any number of them. Call the primes A, B, and C. Take their product and add 1; call the result N. Either N is prime, in which case it is a prime not among A, B, C, since it is larger than all of them. Or N is not prime, in which case it has some prime divisor, say G. Now G cannot be A, B, or C, because each of those divides the product ABC, and a number that divides both ABC and ABC + 1 must divide their difference, which is 1. No prime divides 1. So G is a prime not on the list. In either case, the list was incomplete.

That is the whole proof. The one fact it uses from earlier in the Elements is that every number greater than 1 has a prime divisor, which Euclid had proved in Book VII by taking the smallest divisor greater than 1 and showing it must be prime.

The mistake almost everyone makes

Retold from memory, the proof usually comes out as follows: multiply the first n primes together, add 1, and the result is a new prime. That is false, and the first counterexample is small enough to check by hand. The products of the first few primes plus 1 are 3, 7, 31, 211, and 2311, all prime, which is why the misreading survives. The next one is 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031, and 30031 = 59 × 509. Neither factor is on the list of the first six primes, so Euclid's argument is intact: the list {2, 3, 5, 7, 11, 13} was incomplete, and 59 proves it. What fails is the extra claim that N itself is prime, which Euclid never made. His argument has two cases, and the second case is the one that does the work.

The mistake matters beyond this proof, because it is the mistake of confusing "N has a prime factor not on the list" with "N is a prime not on the list". The first is a theorem; the second is a guess that happens to be right five times in a row. In the same spirit, Fermat guessed that the numbers 2^(2^n) + 1 are all prime after checking five of them, and Euler found that the sixth is 641 × 6700417. Five cases prove nothing, and Unit 1 of the masterclass starts with exactly that lesson.

Why the proof gives no formula

A second thing to notice is what the proof does not deliver. It shows that for every finite list there is a prime missing, but it does not say which prime, where it is, or how large. If you feed it the primes up to 13, it points you at 30031 and says "look inside", and inside you find 59, which is not even the next prime after 13. Euclid's method is an existence proof. It tells you the primes never stop without telling you how to find the next one, and that gap, between knowing something exists and being able to compute it, runs through the whole subject. Two thousand years passed before anyone could say how many primes there are below a given number, even approximately; that is the prime number theorem, and it needed tools Euclid could not have imagined.

A variant that says more

Euclid's trick can be steered. Suppose you want infinitely many primes that leave remainder 3 on division by 4, such as 3, 7, 11, 19, 23. Take any finite list of them, multiply them together, multiply by 4, and subtract 1. The result N leaves remainder 3 on division by 4. Its prime factors are all odd, and they cannot all leave remainder 1 on division by 4, because a product of numbers of the form 4k + 1 is again of that form. So some prime factor of N leaves remainder 3, and it is not on the list, since every listed prime divides N + 1. Hence there are infinitely many primes of the form 4k + 3.

The same device works for primes of the form 6k + 5 and a few other patterns, and then it stops working. For primes of the form 4k + 1 it fails, because a product of numbers of the form 4k + 3 can be of either form. The general statement, that every arithmetic progression a, a + q, a + 2q, ... with gcd(a, q) = 1 contains infinitely many primes, was proved by Dirichlet in 1837 with an entirely different method, and the contrast between the two proofs is the opening of Unit 14 of the masterclass.

Three other proofs

Euclid's is the oldest proof, not the only one, and the alternatives each show the primes from a different side.

Euler's proof of 1737 is quantitative. He considered the product over all primes p of 1/(1 - 1/p). If there were finitely many primes, the product would be a finite number. But expanding each factor as a geometric series 1 + 1/p + 1/p² + ... and multiplying everything out gives, by unique factorization, the sum of 1/n over every positive integer n, which is the harmonic series and diverges. So the product cannot be finite, and the primes are infinite. Pushed a little further, the same argument shows that the sum of the reciprocals of the primes, 1/2 + 1/3 + 1/5 + 1/7 + ..., diverges too, which is a statement no version of Euclid's argument can reach: the primes are not merely infinite, they are not too thin. Unit 8 of the masterclass proves this.

The proof with Fermat numbers, which goes back to a letter from Goldbach to Euler of 1730, uses the numbers F(n) = 2^(2^n) + 1 whose primality Fermat had guessed wrongly. Whether or not they are prime, any two of them are coprime: F(n) - 2 is the product of all the earlier ones, so a common divisor of F(m) and F(n) would divide 2, and the numbers are odd. Each F(n) therefore has a prime factor that none of the others has, and since there are infinitely many Fermat numbers, there are infinitely many primes.

Hillel Furstenberg's proof of 1955 is a curiosity that every student should see once. Define a topology on the integers in which the open sets are unions of arithmetic progressions. Each set of multiples of a prime is closed, and the union over all primes of these sets is every integer except 1 and -1. If there were finitely many primes, that union would be a finite union of closed sets, hence closed, so {1, -1} would be open. But no finite set is open in this topology, since every non-empty open set contains an infinite progression. The argument is Euclid's in disguise, as several people have pointed out, but the disguise is good enough to be worth the price.

Reading the original

The Elements survive in manuscripts copied for two thousand years, and in papyrus scraps from Egypt that are older than any complete manuscript. The oldest surviving diagram from the Elements is on a fragment found at Oxyrhynchus, from around AD 100, now at the Penn Museum in Philadelphia; it shows a proposition from Book II. The number theory is in Books VII to IX, and Proposition IX.20 can be read in English, with Euclid's lettering, in the Heath translation, which is in the public domain and online. The Prime Pages give the proof in a form close to the original and several of the alternatives.

Unit 3 of the masterclass, which is free to read as the sample unit, proves Euclid's theorem, works through the counterexample 30031, and goes on to the fundamental theorem of arithmetic that Euler's proof depends on.

Study the integers properly

The NT Masterclass: weekly units, quizzes, a final exam, and a certificate.
About the program