Thursday, January 29, 2015

An infinitude of primes

Euclid provided a proof for the infinitude of primes.  The following proof is based on his argument:

Theorem 1:  There are an infinite number of primes

(1)  Assume that $p_n$ is the largest prime.
(2)  Let $q = p_n! + 1$
(3)  Since $q > p_n$, $q$ cannot be a prime (by our assumption).
(4)  So, therefore a prime $p$ divides $q$
(5)  But if $p \le p_n$, then $p | p_n!$ and $p | (p_n! + 1) - p_n! = 1$ which is impossible.
(6)  Therefore, we have a contradiction since $p > p_n$ but $p$ is a prime.