Another Proof of the Infinitude of Primes

In this post, we present an alternative proof that there are infinitely many prime numbers in addition to the basic proof presented in the previous post Euclid’s Proof of the Infinitude of Primes. Historically, this alternative proof is due to Christian Goldbach (from a letter to Leonhard Euler in 1730). It is an elegant proof that is worthy to be considered as straight from “The Book” by Paul Erdos (at least “The Approximate Book”). Specifically it is one of the six proofs for the infinitude of primes found in .

This proof of infinitude of primes uses the notion of Fermat numbers. We present the proof in two parts.

For a proof of the infinitude of primes using topology, see The Infinitude of Primes – a Topological Proof.

___________________________________________________________________________________________________________________

Part 1

Theorem 1. There exist infinitely many positive integers $F_0,F_1,F_2,F_3,\cdots$ such that for every $i$ and $j$ with $i, the integers $F_i$ and $F_j$ are relatively prime (i.e. if $m$ divides both $F_i$ and $F_j$, then $m=1$).

The existence of $F_0,F_1,F_2,F_3,\cdots$ implies that there are infinitely many primes. Each $F_i$ has at least one prime factor. Then choose the smallest prime factor $p_i$ for $F_i$. It is clear that $p_i \ne p_j$ for $i (otherwise $F_i$ and $F_j$ would not be relatively prime).

___________________________________________________________________________________________________________________

Part 2

One way to get the integers $F_0,F_1,F_2,F_3,\cdots$ in Theorem 1 is through the Fermat numbers.

A positive integer is a Fermat number if it is of the form $F_n=2^{2^n}+1$ for some non-negative integer $n$. The following two points establish Theorem 1.

1. Each Fermat number can be generated recursively by multiplying all Fermat numbers before it and then add 2. We have the following:
2. $\text{ }$ $\displaystyle \biggl(\prod_{k=0}^{n-1} F_k \biggr) +2=F_n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

3. Each pair of Fermat numbers are relatively prime. $\text{ }$

We can prove the above recursive relation by induction. Clearly $F_0+2=F_1$ (the case for $n=1$). Suppose that the recursive relation $(1)$ holds for $n-1$ where $n>1$. Thus we have $\displaystyle \biggl(\prod_{k=0}^{n-2} F_k \biggr) +2=F_{n-1}$ or $\displaystyle \biggl(\prod_{k=0}^{n-2} F_k \biggr) =F_{n-1}-2$. The following derives the recursive relation $(1)$ for the general case $n$ where $n>1$: \displaystyle \begin{aligned} \biggl(\prod_{k=0}^{n-1} F_k \biggr) +2&=\biggl(\prod_{k=0}^{n-2} F_k \biggr) \times F_{n-1} +2 \\&=\biggl(F_{n-1}-2 \biggr) \times F_{n-1} +2 \\&=\biggl(2^{2^{n-1}}+1-2 \biggr) \times \biggl(2^{2^{n-1}}+1 \biggr) +2 \\&=\biggl(2^{2^{n-1}}-1 \biggr) \times \biggl(2^{2^{n-1}}+1 \biggr) +2 \\&=2^{2^n}-1+2 \\&=2^{2^n}+1=F_n \end{aligned}

We now show that any pair of Fermat numbers are relatively prime. Suppose that $m$ is a common divisor for $F_j$ and $F_n$ where $j. Then $m$ divides both $\displaystyle \prod_{k=0}^{n-1} F_k$ and $F_n$. Because of the recursive relation $(1)$, $m$ divides 2. Since the Fermat number $F_n$ is an odd integer, $m$ cannot be 2. Thus $m=1$.

Thus the Fermat numbers satisfy Theorem 1.

See here for a generalization of the proof in this post, without the Fermat number point of view.

___________________________________________________________________________________________________________________

Reference

1. Aigner, M., Gunter, M.Z. Proofs from THE BOOK, third edition, Springer-Verlag, Berlin, 2004.

___________________________________________________________________________________________________________________ $\copyright \ 2013 \text{ by Dan Ma}$