Euclid's Proof of the Infinitude of Primes (c. 300 BC)

By Chris Caldwell

Euclid may have been the first to give a proof that there are infinitely many primes.  Even after 2000 years it stands as an excellent model of reasoning.  Below we follow Ribenboim's statement of Euclid's proof [Ribenboim95, p. 3], see the page "There are Infinitely Many Primes" for several other proofs.

Theorem.

There are infinitely many primes.

Proof.

Suppose that p₁=2 < p₂ = 3 < ... < p_r are all of the primes. Let P = p₁p₂...p_r+1 and let p be a prime dividing P; then p can not be any of p₁, p₂, ..., p_r, otherwise p would divide the difference P-p₁p₂...p_r = 1, which is impossible. So this prime p is still another prime, and p₁, p₂, ..., p_r would not be all of the primes. ∎

It is a common mistake to think that this proof says the product p₁p₂...p_r+1 is prime.  The proof actually only uses the fact that there is a prime dividing this product (see primorial primes).

The proof above is actually quite a bit different from what Euclid wrote.  We now understand the integers as abstract objects, but the ancient Greeks understood them as counts of units (the unit, one, was not a number, two was thier first) and represeted them with lengths of line segments (multiples of some unit line segment).  Where we talk of divisibility, Euclid wrote of "measuring," seeing one number (length)a as measuring (dividing) another length b if some integer numbers of segments of length a makes a total length equal to b.

The ancient Greeks also did not have our modern notion of infinity.  School children now easily understand lines as infinite, but the ancients were again more concrete (in this regard).  For example, they viewed lines as segments that could be extended indefinitely (not something infinite that we view just part of).  For this reason Euclid could not have written "there are infinitely many primes," rather he wrote "prime numbers are more than any assigned multitude of prime numbers."

Finally, Euclid sometimes wrote his "proofs" in a style which would be unacceptable today--giving an example rather than handling the general case.  It was clear he understood the general case, he just did not have the notation to express it.  His proof of this theorem is one of those cases.

Below is a proof closer to that which Euclid wrote, but still using our modern concepts of numbers and proof.  See David Joyce's pages for an English translation of Euclid's actual proof. 

Theorem.

There are more primes than found in any finite list of primes.

Proof.

Call the primes in our finite list p₁, p₂, ..., p_r.  Let P be any common multiple of these primes plus one (for example, P = p₁p₂...p_r+1).  Now P is either prime or it is not.  If it is prime, then P is a prime that was not in our list.  If P is not prime, then it is divisible by some prime, call it p.  Notice p can not be any of p₁, p₂, ..., p_r, otherwise p would divide 1, which is impossible.  So this prime p is some prime that was not in our original list.  Either way, the original list was incomplete. ∎

Note that what is found in this proof is another prime--one not in the given initial set.  There is no size restriction on this new prime, it may even be smaller than some of those in the initial set.  For example, if we begin with the set:

{ 2, 3, 7, 43, 13, 139, 3263443 },

then the smallest choice of P is the product of these seven primes plus one, so P = 547^.607^.1033^.31051.  The new prime found would be 547, 607, 1033 or 31051, all of which are smaller than the last prime in the original set.