# 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.

**Lemma.**- The Fermat numbers F
_{n}= are pairwise relatively prime. **Proof.**- It is easy to show by induction that
F
_{m}-2 = F_{0}^{.}F_{1}^{.}...^{.}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_{1}=*a*,

a_{2}=a_{1}+*b*,

a_{3}=a_{1}a_{2}+*b*,

a_{4}=a_{1}a_{2}a_{3}+*b*,

...

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

a_{1}=2 and a_{n+1}=
a_{n}^{2}-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.