# Tweaking a proof of the infinitude of primes

This blog presents two proofs of the infinitude of primes. The first one is the standard proof that is due to Euclid (around 300 BC). The second one is due to Christian Goldbach (from a letter to Leonhard Euler in 1730). This post attempts to generalize the second one. The goal is to capture the essence of the proof and in the process gains a better perspective. Reading the second proof is not a prerequisite. The reader is welcome to compare the argument here with the previous proof to appreciate the economy that is in the tweaked proof.

____________________________________________________________________________

The Tweak

The existence of the following sequence will imply that there are infinitely many prime numbers.

There is a sequence of positive odd integers $x_0,x_1,x_3, \cdots$ such that

• $x_0 < x_1 < x_3 < \cdots$,
• any two elements of the sequence are relatively prime, i.e. for $i \ne j$, the terms $x_i$ and $x_j$ have no common divisor other than 1.

If such a sequence exists, we can infer an infinite sequence of prime numbers. Note that each term $x_j$ is a product of distinct primes. Let $p_j$ be the smallest prime factor of $x_j$. The prime numbers $p_j$ must be distinct since the elements in the sequence $x_0,x_1,x_3, \cdots$ are pairwise relatively prime.

How do we know if such a sequence exists? It can be defined recursively. Let $x_0 be any odd positive integers that are relatively prime. For example, $x_0=3$ and $x_1=5$. Another example: $x_0=21$ and $x_1=55$. Then for each $n>1$, let $x_n=x_0 \times x_1 \times \cdots \times x_{n-1}+2$. Clearly the sequence is increasing. To see that any two terms of the sequence are relatively prime, let $j and let $d$ be a common divisor of $x_j$ and $x_n$. Since $d$ divides $x_j$, it is clear that $d$ divides $x_0 \times x_1 \times \cdots \times x_{n-1}$. This means that $d$ divides $x_n-x_0 \times x_1 \times \cdots \times x_{n-1}=2$. With $d$ being odd and $d$ dividing 2, it must be that $d=1$.

The proof in the previous post essentially uses the above argument with the first two terms fixed at $x_0=3$ and $x_1=5$. With these two initial choices, it can be shown that the sequence $x_0,x_1,x_3, \cdots$ consists of the Fermat numbers. It is nice to know that the resulting sequence consists of the Fermat numbers. However, for proving that primes are infinite, the fact about Fermat numbers is immaterial. For example, if the initial two terms are $x_0=21$ and $x_1=55$, the same argument will still lead to an infinite sequence of prime numbers. Using Fermat numbers is one way to derive the sequence in question. Sometimes a broader picture picture can be obscured by being too specific in the argument.

____________________________________________________________________________

An Equivalent Statement

The above argument for the infinitude of primes points to the fact that the existence of an infinite sequence of prime numbers is reduced to the existence of a sequence as described in the above argument. We have the following theorem.

Theorem
The following two statements are equivalent.

• There exists a sequence of positive odd integers $x_0,x_1,x_3, \cdots$ such that $x_0 < x_1 < x_3 < \cdots$ and such that any two terms of the sequence are relatively prime.
• There are infinitely many prime numbers.

It is clear that if there are infinitely many primes, the sequence $x_0,x_1,x_3, \cdots$ can simply be made the primes. So one direction is obvious. The other direction is proved by the above argument.

The theorem essentially says that the “infinity” of primes is identical to the “infinity” of numbers that are pairwise relatively prime. Of course, the purpose of discussing the latter is to give an argument that there are infinitely many primes.

____________________________________________________________________________ $\copyright \ 2016 \text{ by Dan Ma}$