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 existence of the following sequence will imply that there are infinitely many prime numbers.
There is a sequence of positive odd integers such that
- any two elements of the sequence are relatively prime, i.e. for , the terms and 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 is a product of distinct primes. Let be the smallest prime factor of . The prime numbers must be distinct since the elements in the sequence are pairwise relatively prime.
How do we know if such a sequence exists? It can be defined recursively. Let be any odd positive integers that are relatively prime. For example, and . Another example: and . Then for each , let . Clearly the sequence is increasing. To see that any two terms of the sequence are relatively prime, let and let be a common divisor of and . Since divides , it is clear that divides . This means that divides . With being odd and dividing 2, it must be that .
The proof in the previous post essentially uses the above argument with the first two terms fixed at and . With these two initial choices, it can be shown that the sequence 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 and , 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.
The following two statements are equivalent.
- There exists a sequence of positive odd integers such that 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 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.