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.