Around the year 300 BC, Euclid proved that there are infinitely many prime numbers. His proof is straightforward: suppose there are only finitely many primes, say \(p_1,p_2,\dots,p_m\). Then, the number \(Q:=p_1p_2\cdots p_m+1\) is not divisible by any of the primes in the finite list (if it was, then this prime would equal \(1\)!). Thus, either \(Q\) is a new prime not in our list or is divisible by a prime not in our list. This is a contradiction, so there are infinitely many primes.
The simplicity of this proof is certainly striking. One could go further and ask if there are infinitely many primes of a certain form. This page focuses on primes of the form \(kn+\ell, n\geqslant 0\), for two fixed positive integers \(k\) and \(\ell\). Moreover, we are interested in giving a proof of the infinitude of such primes in a way that mimics Euclid's proof.
This type of proof, however, is not available for every value of \(k\) and \(\ell\). To start with, it is well-known that the arithmetic progression \( kn+\ell, n\geqslant 0\), contains infinitely many primes if and only if \( \gcd(k,\ell)=1\). In these cases, a “Euclidean proof” can be found if additionally \( \ell^2\equiv 1\pmod{k}\) (in fact, this is the only case where such a proof can be settled). If one is curious to find out the math behind this statement, check my BSc Thesis in Mathematics.
Here's how to use the webpage:
Off you go! Enjoy the proof!