Infinitely Many Primes

Theorem

There are infinitely many prime numbers.

Proof

Suppose for the sake of contradiction that there are finitely many primes $p_1,p_2,...,p_k$. Consider

$$ \begin{align} M = p_1p_2...p_k + 1. \end{align} $$

Clearly $M > p_i$ for all $i = 1,2,\ldots,k$. Now observe that none of these primes $p_1, p_2,...,p_k$ can divide $M$. This is because if any of these primes did, say it was $p_i$, then

$$ \begin{align} p_i \mid M = p_1p_2...p_k + 1. \end{align} $$

But we know that $p_i$ also divides the product $p_1p_2...p_k$. Therefore, since $p_i \mid M$ and $p_i | p_1p_2...p_k$, then

$$ \begin{align} p_i \mid M - p_1p_2...p_k = 1. \end{align} $$

which is impossible since $p_i > 1$ for all $i = 1,2,\ldots,k$. Hence, none of the primes $p_1,p_2,\ldots,p_k$ can divide $M$. By the Fundamental Theorem of Arithmetic, $M$ must either be prime or a product of primes. Therefore, there must be another prime not in the list dividing $M$ or $M$ itself is a prime not in the list. This is a contradiction and so we can conclude that there are infinitely many primes. $\ \blacksquare$

References

Number Theory by George E. Andrews

</div> Proof