Proof of infinitely many primes

A new paper was posted on Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 B.C.--2012) and another new proof. Euclid's theorem is also proved on The Prime Pages and MathWorld.

This great theorem is both brilliant and trivial, but unfortunately explanations of it tend to get sidetracked into subtleties about infinity, contradiction, and non-constructive proofs. Euclid himself did not understand the concept of infinity. The simplest proof is to turn it into a finitary constructive statement.

Theorem. Let N be the product of a set of primes. If there are no other primes less than N, then N+1 is prime.

Proof. The only possible prime factors of N+1 are in the original set of primes, but those all leave a remainder of 1 when divided into N+1.

Corollary. There are infinitely many primes.

Proof. Given any finite set of primes that purports to be all primes, the theorem contructs another one.

This is essentially the same as Euclid's proof, but if you don't say it right, then N+1 is not necessarily a prime. For example, 2*3*5*7*11*13 + 1 = 59*509. So most proofs need extra explanations to address this point. However, the above proof avoids the issue.

This presentation also exemplifies the difference between hard and soft analysis. The distinction is similar to that of hard and soft science, but for math it is more subtle. The authority on the analysis distinction is Terry Tao, who explained it here in 2007 and here in 2011. On his blog, he often tries to turn a soft theorem into a hard theorem.

The above theorem is hard, while the corollary is soft. The theorem is hard because it is finitary. Given some set of primes, it tells you how to find another one. The operation can be carried out in some finite and predictable number of computations.

The corollary is soft because it says nothing about how those primes are distributed, or how to find them, or how big they are, or anything beyond there being infinitely many. Yes, you can get all the primes by counting the natural numbers and testing each one for primality. But the corollary gives no clue about how much work you will have to do to find each prime. While everyone agrees that the corollary is a true and meaningful statement, the theorem is saying something more precise that might be more useful in some situations.

This presentation is also a good example of how a difficult theorem (that there are infinitely many primes) is made easy by merely formulating the right lemma. Once the above theorem about N+1 being prime is formulated, it is easy to prove it, and to prove Euclid's theorem.

Note also that the hard-soft distinction is not the same as the difficult-easy distinction. Hard analysis is hard because of its rigidity, not its difficulty.

Update: For completeness, I give G.H. Hardy's version:

The first is Euclid’s proof of the existence of an infinity of prime numbers. ... We have to prove that there are infinitely many primes, i.e. that the series (A) never comes to an end.

Let us suppose that it does, and that

2, 3 , 5 , …, P

is the complete series (so that P is the largest prime); and let us, on this hypothesis, consider the number Q defined by the formula

Q = (2· 3 · 5 · … P) + 1

It is plain that Q is not divisible by and of 2, 3, 5, …, P; for it leaves the remainder 1 when divided by any one of these numbers. But, if not itself prime, it is divisible by some prime, and therefore there is a prime (which may be Q itself) greater than any of them. This contradicts our hypothesis, that there is no prime greater than P; and therefore this hypothesis is false.

The proof is by reductio ad absurdum, and reductio ad absurdum, which Euclid loved so much, is one of a mathematician’s finest weapons. It is a far finer gambit than any chess gambit: ... (The proof can be arranged so as to avoid a reductio, and logicians of some schools would prefer that it should be.)

This is the soft version of the proof. The core reasoning is essentially the same, but you have to read the proof to extract a finitary argument.

Euclid's original argument did not use contradiction or consecutive primes as Hardy described. It was more similar to the above hard proof.