# A Hand-wavy Proof for the Infinitude of Prime Numbers


Recently while reading
[Gödel, Escher, Bach](https://www.goodreads.com/book/show/24113.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](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes),
and I vaguely remember that even really large primes remain
[somewhat evenly spaced](https://www.quantamagazine.org/yitang-zhang-proves-landmark-theorem-in-distribution-of-prime-numbers-20130519/).

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](https://en.wikipedia.org/wiki/Euclid%27s_theorem#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](https://unsplash.com/photos/XfOVP3y_ZdM)_