Recently while reading Gödel, Escher, Bach, I learned about a neat proof for a rather intuitive fact: there are an infinite number of prime numbers. For whatever reason, prime numbers pop up in computer science frequently (or, at least, in computer science textbook examples and interview questions, for those of us that don’t work in cryptography), so I considered myself to be reasonably familiar with them.

I’ve written prime checkers, I’m familiar with the Sieve of Eratosthenes, and I vaguely remember that even really large primes remain somewhat evenly spaced.

However, most of that is received knowledge. I don’t think I could derive the Sieve of Eratosthenes from first principles, or produce really any optimizations on a naive prime checker other than only checking for divisors less than $\sqrt{N}$.

All this to say, I enjoyed reading through Euclid’s proof of the infinitude of primes, which shows mathematically why there are an infinite number of prime numbers.

What follows is a pretty hand-wavy recap of this proof, as taken from Chapter II of Gödel, Escher, Bach:

  • Recall that a prime number is any positive, natural number which is only divisible by $1$ and itself.
  • To show that there are infinitely many primes, we will show that for some positive natural number $N$, there exists a prime number that is greater than $N$.
  • Recall that the definition of $x!$ (“x factorial”) is $\prod_{i=1}^x i$. Put another way: $x! = 1 * 2 * … * x$.
  • Consider the number $(N!+1)$. It cannot have a divisor other than $1$ in the range $[1, N]$, because $N!$ contains the product of all numbers in that range. For example, $N!+1$ will have remainder $1$ with $2$, remainder $1$ with $3$, and so on.
  • Then, there are two cases. Either, $(N!+1)$ is prime, in which case we’re done. If $(N!+1)$ is not prime, this implies that there is some prime number in the range $[N+1, N!]$ that is prime. In either case, we show that given an arbitrary $N$, we can always generate a prime larger than it.
  • Since we allow arbitrary choice of $N$, and in all cases we show that there exists a prime number larger than $N$, it becomes trivial to prove inductively that there are an infinite number of prime numbers.

Pretty neat, huh?

Cover Photo: Unsplash