Goldbach's Proof of the Infinitude of Primes (1730)
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.
- The Fermat numbers Fn = are pairwise relatively prime.
- It is easy to show by induction that Fm-2 = F0.F1.....Fm-1. This means that if d divides both Fn and Fm (with n < m), then d also divides Fm-2; so d divides 2. But every Fermat number is odd, so d is one. ∎
Now we can prove the theorem:
- There are infinitely many primes.
- Choose a prime divisor pn of each Fermat number Fn. 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 an as follows.
This includes both the Fermat numbers (with a=1,b=2) and Sylvester's sequence (with a=1,b=2):
a1=2 and an+1= an2-an+1.
In fact, the proof really only needs a sequence which has a subsequence which is pairwise relatively prime, e.g., the Mersenne numbers.