This post was originally published 30 September 2018
I heard about a very cool proof of the infinitude of primes listening to the wonderful My Favorite Theorem podcast. The guest on episode 22 is Ken Ribet who is well known in the larger mathematical community because he contributed to the mathematics that led up to the proof of Fermat’s Last Theorem, but he chose for his episode of My Favorite Theorem to talk about the infinitude of prime numbers.
Euclid’s Proof
The theorem is attributed to Euclid, and the classical proof goes like this. Suppose that there are only finitely many primes. Let’s call them
$$p_1, p_2, \ldots , p_k.$$
Then define the number $N$ to be
This means we are taking the product of all the finitely many prime numbers, and then adding one. Now, is the number $N$ prime, or is it composite (i.e. the product of more than one prime)? It must be composite because it is larger than all the primes: each prime is greater than one, and so the product is larger than any of the $k$ prime numbers. The fundamental theorem of arithmetic says that all integers can be factored (uniquely up to reordering) as the product of primes (or they are prime themselves). So what primes factor $N$? Well because we added that one to the product when we defined $N$, then none of $$p_1, \ldots , p_k$$ divides $N$ evenly. To summarize, N is a composite number that has no prime factors – a contradiction. Our initial assumption that there are only $k$ prime numbers must be incorrect. Great!
This proof has a somewhat awkward structure: we assume the opposite of what we want to prove, and then argue until there is a contradiction. This is what is called a proof by contradiction, and despite the fact that mathematicians use this type of proof all the time, they tend to complain about them. It’s like the mathematical equivalent of ending a sentence with a proposition or splitting an infinitive: totally normal, but some say that it’s bad style.
Another Proof
Ribet describes another proof of the infinitude of prime numbers. His proof comes from a paper appearing in the American Mathematical Monthly by Eckford Cohen. The paper begins by stating the Legendre Identity
$$ e_p(n!) = \sum _{k>0} \left[ \frac{n}{p^k} \right] .$$
There is a lot to unpack here, and some definitions are required. First, in the left hand side $e_p(m)$ means the largest power of $p$ that divides $m$ (without a remainder). So if $e=e_p(m)$, then $p^e$ divides $m$, but $p^{e+1}$ doesn’t divide $m$. The Legendre Identity is about the largest power of $p$ that divides $n!=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$.
On the right hand side we have the greatest integer function $[x]$ which means take the number $x$ and round down.
A Quick Example
Let’s see an example with $p=3$ and $n=5$.
First of all, $$ 5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120 = 3 \cdot 40.$$ I’m writing $5! = 3 \cdot 40$ because $3$ doesn’t divide $40$, so the factor $3$ is the biggest power of $3$ that divides $5!$. So $$ e_3(5!) = 1.$$
On the other hand, $$\frac{5}{3^1} = \frac{5}{3} \approx 1.67,$$ and $$\frac{5}{3^2} = \frac{5}{9} \approx 0.56.$$
So $$ \left[ \frac{5}{3} \right] = 1,$$ and $$ \left[ \frac{5}{3^k} \right] = 0$$ for all $k \geq 2$. Putting this together in the context of the Legendre Inequality
$$ e_3(5!) = 1 = \left[ \frac{5}{3} \right].$$
You can verify for yourself that $e_2(5!)=3$ and check the right hand side of the Legendre identity.
Back to the Proof
It’s not at all obvious what this has to do with there being infinitely many primes. This is one of the cool things about mathematics and number theory – interesting results seem to come from unexpected places.
If you are curious, you can read a proof of the Legendre Identity in the Monthly article, but let’s accept it, and get to the proof of the infinitude of primes.
We want to turn the Legendre identity into an inequality: $$ e_p(n!) = \sum _{k>0} \left[ \frac{n}{p^k} \right] \leq n \sum _{k>0} \frac{1}{p^k} = n \cdot \frac{1}{p} \cdot \frac{1}{1-\frac{1}{p}} = \frac{n}{p-1}.$$
Here, I’m using the formula to sum a geometric series $$\sum _{k=0}^{\infty} x^k = \frac{1}{1-x},\quad | x| < 1.$$ In our case $x = frac{1}{p}$ and we are starting the sum with $k=1$ instead of $k=0$ hence the extra factor of ${1}{p}$. To make this easer to read I reproduce the important part below: $$ e_p(n!) \leq \frac{n}{p-1}.$$
Next, we want to write $$n~ = \prod _{p\leq n} p^{e(n!)}.$$
The right hand side is the product over all prime numbers less than or equal to $n$. The only point to mention here is that we can restrict to $p \leq n$ rather than $p$ dividing $n!$ because for a prime $p$ to divide $n!$, it must divide one of the integers $1, \ldots, n$ and that means that $p \leq n$. Then take the $n$th root of both sides of the equation giving
$$ \sqrt[n]{n!} = \prod _{p \leq n} \sqrt[n]{p^{e(n!)}} \leq \prod _{p \leq n} \sqrt[n]{p^{\frac{n}{p-1}}} = \prod _{p \leq n} p^{\frac{1}{p-1}}.$$
It’s well known that $\lim _{n \rightarrow \infty} \sqrt[n]{n!} = \infty$, meaning that we can make $\sqrt[n]{n!}$ as big as we want by choosing larger and larger $n$. That implies that we can make the right hand side as big as we want by choosing larger and larger $n$, too. The right hand side is a product over prime numbers, and each factor stays the same as we increase $n$. It’s just that we are includeing more and more primes in the product. This means there have to be infinitely many primes so that we can keep making the right hand side bigger. QED.