Euclid’s Proof of the Infinitude of Primes

The oldest known proof that there are infinite number of primes is the one that is due to Euclid (around 300 BC). It is probably the most accessible. So I start the blog by stating this proof.

________________________________________________________

Theorem. There are infinitely many prime numbers.

The strategy is to show that given a finite list of prime numbers $\left\{p_1, p_2, \cdots, p_n \right\}$, we can always find another prime number not on the list.

Let $n=p_1 \times p_2 \times \cdots \times p_n$. Let $p$ be a prime divisor of $n+1$. If $p$ is on the list $\left\{p_1, p_2, \cdots, p_n \right\}$, then $p$ would divide both $n+1$ and $n$. This means that $p$ would divide 1 (the difference of $n$ and $n+1$). This is impossible. So $p$ must a prime number not on the original list. Hence there must be infinitely many prime numbers.

________________________________________________________ $\copyright \ 2013 \text{ by Dan Ma}$ $\text{ }$