Proof of the infinitude of primes

Theorem: There are infinitely many prime numbers.

Proof: Suppose not. Assume toward contradiction that there exists a finite set of all prime numbers: $P_{n}=\left \{ p_{1},p_{2},...\,, p_{n}\right \}$.
Let $M \epsilon \,\mathbb{N}= \prod _{i=1}^{n} p_{i}$. Consider $N = 1 + M > 1$.

By the Fundamental Theorem of Arithmetic, there must exist some prime $p_{i} \,\epsilon \, P$ such that $(M\mod \,p_{i}) = (N\mod \,p_{i}) = 0$. But, this is impossible, as, for all i, $p_{i} > 1$ and $N – M = 1$.

Thus, by contradiction the set P of all prime numbers cannot be finite.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License