My Favourite Proof

This post is inspired and adapted from Greg Martin's excellent talk on prime numbers (found here).

As a student of mathematics, one of the first things I ever learned was the concept of a proof. In fact, the first proof I ever saw was Euclid's classic proof that there were an infinite number of primes.

If you have never seen Euclid's proof before, it goes something like this:

Suppose there were a finite number of primes. We may label them $p_1, p_2, \ldots, p_n$. Let \[N=p_1 p_2 \ldots p_n + 1.\] Now for every prime $p_i,\,1\leq i\leq n$ that we just labelled, the remainder of $N$ divided by $p_i$ is 1. However, since $N$ is not prime, $N$ must be able to be factorized into a product of primes. What primes are in that factorization if it doesn't contain any of the primes we just listed out?

Hence, $N$ must have some new prime in its factorization or be a prime itself. This contradicts our assumption that there are a finite number of primes, and therefore an infinite number of primes must exist. $\blacksquare$

Recently, I learned that a variant of Euclid’s proof can be used to prove the infinitude of primes of the form 4k-1 and 6k-1. The proof for 4k-1 is below:

Suppose there are a finite number of primes that is of the form 4k-1 for some $k\in\mathbb{N}$. Again, we may label them $p_1, p_2, \ldots, p_n$. Let   \[N=4 p_1 p_2 \ldots p_n - 1.\] Again, for every prime $p_i,\,1\leq i\leq n$ that we just labelled, the remainder of $N$ divided by $p_i$ is 1. Note that $N$ is not prime since it is of the form 4k-1 but greater than any of our $p_i$. However, since $N$ is not a prime, $N$ must be able to be factorized into a product of primes. 

Furthermore, the factorization of $N$ must only contain primes of the form 4k+1 since $N$ is odd and all primes of the form 4k-1 are used. This is a contradiction since two numbers which are of the form 4k+1 must have a product of the form 4k+1. Hence, if $N$ was entirely the product of primes of the form 4k+1, $N$ must be a number of the form 4k+1 also. But since $N$ is obviously not expressible as 4k+1, $N$ must itself be a prime that is of the form 4k-1 or have some new prime factor that is of the form 4k-1. Again, by contradiction, there must exist an infinite number of primes of the form 4k-1. The case for 6k-1 is similar. $\blacksquare$

Amazingly, there is a general theorem which states that a Euclid-style proof can only be used to prove the infinitude of primes of the form $p \equiv a\bmod{m}$, where $a^2 \equiv 1 \bmod{m}$ for any two natural numbers $a$ and $m$ (proven here by Murty, 1988). For example, this means that infinitude any primes of the form $p \equiv -1 \bmod 4$ may be proven (as we did above), but any primes of the form $p \equiv 3 \bmod 7$ cannot be proven by Euclid's proof.

I find Euclid’s classic proof of the infinitude of primes beautiful -- not just because it establishes an amazing result in an elegant way, but because of its vast reusability. For these reasons, it is easily my favourite proof.

Bonus: From the theorem above, we may also prove infinitude of primes of the form 4k+1 by a Euclid style proof. Try proving this statement! Be warned though, there is an extra trick to defining $N$ than just multiplying all primes of the form 4k+1 together. The solution can be found in the slides of Greg Martin, as referenced in the first sentence of this post.