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<x_1 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<n 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}

Advertisements

2 thoughts on “Tweaking a proof of the infinitude of primes

  1. Pingback: Another Proof of the Infinitude of Primes | Exploring Number Theory

  2. Pingback: Fermat numbers | Exploring Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s