Goldbach's Proof of the Infinitude of Primes (1730)

By Chris Caldwell

Euclid may have been the first to give a proof that there are infintely many primes, but his proof has been followed by many others. Below we give Goldbach's clever proof using the Fermat numbers (written in a letter to Euler, July 1730), plus a few variations. See the page "There are Infintely Many Primes" for several more proofs.

First we need a lemma.

Lemma.: The Fermat numbers F_n = are pairwise relatively prime.
Proof.: It is easy to show by induction that F_m-2 = F₀^.F₁^....^.F_m-1. This means that if d divides both F_n and F_m (with n < m), then d also divides F_m-2; so d divides 2. But every Fermat number is odd, so d is one. ∎

Now we can prove the theorem:

Theorem.: There are infinitely many primes.
Proof.: Choose a prime divisor p_n of each Fermat number F_n. By the lemma we know these primes are all distinct, showing there are infinitly many primes. ∎

Note that any sequence that is pairwise relatively prime will work in this proof. This type of sequence is easy to construct. For example, choose relatively prime integers a and b, then define a_n as follows.

a₁=a,
a₂=a₁+b,
a₃=a₁a₂+b,
a₄=a₁a₂a₃+b,
...

This includes both the Fermat numbers (with a=1,b=2) and Sylvester's sequence (with a=1,b=2):

a₁=2 and a_n+1= a_n²-a_n+1.

In fact, the proof really only needs a sequence which has a subsequence which is pairwise relatively prime, e.g., the Mersenne numbers.