Today, we take a break from our recent philosophical musings to return to some good old-fashioned mathematics (indeed, the mathematics today could be seen as all being “old-fashioned,” as the theorem we will be considering dates back to the ancient Greeks).

I’m sure my readers have all been introduced to the prime numbers, but, to refresh any memories, let me remind you that a prime number is a natural number, at least 2, that has no divisors other than 1 and itself. The first few prime numbers are, therefore: 2, 3, 5, 7, 11, 13…

The prime numbers can be thought of as the building blocks of number theory, as the backbone of the natural numbers. They have occupied a central place in mathematics and offered endless fascination for millennia. They are a source of great mystery even today.

In this post, we look at a classic theorem, commonly attributed to Euclid. Euclid’s proof is one of the gems of mathematics, a proof that is taught to every mathematician at the beginning of their true mathematical career. The theorem, as we will state it, is simply this:

Euclid’s Theorem: There are infinitely many prime numbers.

Euclid himself did not state the theorem in exactly this form, perhaps because of the ancient Greeks’ general antipathy towards the existence of infinite sets. He instead put forward the equivalent statement, “For every finite set of prime numbers, there is a prime number not in that set.”

Euclid’s Theorem has collected a vast and varied array of delightful proofs throughout the years, and, in a proposed infinite series of blog posts, I plan to cover all of them. Today, we will look at three proofs, from three very different centuries, all using only elementary number-theoretic techniques. First, of course, is Euclid’s proof itself.

Proof One (Euclid): Suppose that P = \{p_0, p_1, \ldots, p_n\} is a finite set of prime numbers. We will show that there is a prime number that is not in P. To do this, let q = p_0p_2\ldots p_n, and let r = q+1. For all i \leq n, p_i divides q with no remainder (as q = p_i(p_0\ldots p_{i-1}p_{i+1}\ldots p_n)), so, as r = q+1 and p_i \geq 2, p_i does not divide r. Since r > 1 and every integer greater than 1 has prime divisors, there is at least one prime, p^*, that divides r. But we just saw that no element of P divides r, so p^* is a prime that is not in P.


The next proof we will consider is due to the eighteenth-century German mathematician Christian Goldbach, largely known today for the statement of the still unproven Goldbach’s Conjecture. This proof (like Goldbach’s Conjecture itself) appears in a letter from Goldbach to Leonhard Euler (whose analytic proof of Euclid’s Theorem we will visit in a future post).

Proof Two (Goldbach): For each natural number n, let F_n = 2^{2^n} + 1, so F_0 = 3, F_1 = 5, F_2 = 17, etc. (F_n is known as the n^{\mathrm{th}} Fermat number.)

Claim 1: For every natural number n, F_{n+1} = F_0F_1\ldots F_n + 2.

Proof of Claim 1: Suppose that the Claim is false, and let n be the smallest natural number such that F_{n+1} \neq F_0F_1 \ldots F_n + 2. Since the Claim can easily be verified by inspection for n=0, we may assume n > 0. But now we have the following sequence of calculations where, because we are assuming that n is the smallest counterexample to the Claim, we can use the fact that F_n = F_0F_1\ldots F_{n-1} + 2.

\begin{array}{rcl}F_{n+1} & = & 2^{2^{n+1}}+1 \\ & = & 2^{2^n}\cdot 2^{2^n} + 1 \\ & = & (F_n-1)(F_n-1)+1 \\ & = & (F_n)(F_n) - 2F_n + 2 \\ & = & (F_n)(F_0F_1\ldots F_{n-1} + 2) -2F_n + 2 \\ & = & F_0F_1\ldots F_n + 2F_n - 2F_n + 2 \\ & = & F_0F_1\ldots F_n + 2 \end{array}

But this calculation shows that n is not a counterexample to our Claim, contradicting our assumption and finishing the proof of the Claim.

We now need a very simple number-theoretic Claim.

Claim 2: If a and b are natural numbers, p is a prime, and p divides both a and a+b, then p divides b.

Proof of Claim 2: Suppose a = mp and  a+b = np, where m and n are natural numbers. Then b = a+b-a = np - mp = (n-m)p, so p divides b.

Claim 3: If m < n are natural numbers, then there is no prime number p such that p divides both F_m and F_n.

Proof of Claim 3: Suppose that the Claim is false and that there are natural numbers m < n and a prime number p such that p divides both F_m and F_n. Note that F_m is one of the factors in the product F_0F_1\ldots F_{n-1}, so p divides F_0F_1\ldots F_{n-1}. Since F_n = F_0F_1\ldots F_{n-1} + 2, we also conclude that p divides F_0F_1\ldots F_{n+1} + 2, so, by Claim 2, we know that p divides 2. As 2 is prime, this means that p = 2. But F_m and F_n are both odd, so this is impossible.

We are now ready to finish the proof. For each natural number n, choose a prime number p_n that divides F_n. By Claim 3, for all natural numbers m < n, we have p_m \neq p_n, so \{p_n \mid n \in \mathbb{N}\} is an infinite set of prime numbers.

Remark: The Fermat numbers were introduced, unsurprisingly, by the seventeenth-century French mathematician Pierre de Fermat (of Fermat’s Last Theorem fame). Fermat conjectured that every Fermat number is in fact prime (this would obviously imply Claim 3 from the previous proof). The first four Fermat numbers (3, 5, 17, 257) are easily verified to be prime, and the next Fermat number, 65537, can be seen to be prime with a bit more work. However, Euler proved in 1732 that F_5 is not prime. Indeed, F_5 = 2^{32}+1 = 4294967297 = 641 \times 6700417. Many mysteries remain regarding the Fermat numbers. For example, even the following two very basic questions remain unsolved to this day:

  • Are there infinitely many prime Fermat numbers?
  • Are there infinitely many non-prime Fermat numbers?

The Fermat numbers grow so quickly that, even with computers, it can be hard to analyze even “relatively small” Fermat numbers. For example, it is unknown whether F_{20} or F_{24} are prime. On the other hand, the truly gigantic number F_{3329780} is known to be non-prime: one of its prime factors is 193 \times 2^{3329780} + 1.


Finally, a proof that combines ideas from Euclid’s and Goldbach’s proofs was given recently by Filip Saidak.

Proof Three: (Saidak) Note first that, for every natural number n, we have that n and n+1 do not have any shared prime divisors. Now define an infinite sequence of natural numbers, \langle n_0, n_1, \ldots \rangle as follows. Let n_0 be any natural number that is at least 2. Let n_1 = n_0(n_0+1). Since n_0 and n_0 + 1 do not share any prime divisors, and since both n_0 and n_0+1 have at least one prime divisor, it follows that n_1 must have at least 2 distinct prime divisors.

Now let n_2 = n_1(n_1+1). Again, n_1 and (n_1 + 1) do not have any shared prime divisors. We have shown that n_1 has at least 2 distinct prime divisors, and we know that n_1 + 1 has at least one prime divisor, so n_2 must have at least 3 distinct prime divisors. Continuing in this way, defining n_{k+1} = n_k(n_k+1) for every natural number k, one proves that, for each natural number k, the number n_k has at least k+1 distinct prime divisors. In particular, there are infinitely many prime numbers.


Stay tuned for a future post, in which we will provide proofs of Euclid’s Theorem from further flung areas of mathematics, including real analysis and topology.

Advertisements

One thought on “An Infinitude of Proofs, Part 0

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