Proof that there are Infinitely Many Primes

Lemma 1: Every integer $N \geq 2$ has a prime divisor.

• Proof: If $N$ is prime then $N$ has itself as a prime divisor.

• So assume that $N$ is a composite number. Then there exists integers $a_1$ and $b_1$ with $1 < a_1 < N$ and $1 < b_1 < N$ such that $N = a_1b_1$

• If either $a_1$ or $b_1$ is prime then we are done - as $N$ has a prime divisor. If both $a_1$ and $b_2$ are composite then consider $a_1$. Then there exists integers $a_2$ and $b_2$ with $1 < a_2 < a_1$ and $1 < b_2 < a_1$ such that $a_1 = a_2b_2$.

• If either $a_2$ or $b_2$ is prime then we are done - as $N$ has a prime divisor. If both $a_2$ and $b_2$ are composite then consider $a_3$ and repeat the process above.

• Observe that $1 < ... < a_3 < a_2 < a_1 < N$ and since $N$ is a finite number, this process must eventually terminate, i.e., $N$ has prime divisor. $\blacksquare$

Theorem 2 (Euclid): There exists infinitely many primes.

• Proof: Suppose instead that there exists only finitely many primes - label them $p_1$, $p_2$, …, $p_n$. Consider the product of all of these primes $+ 1$ and call it $N$:

(1)

\begin{align} \quad N = p_1 \cdot p_2 \cdot ... \cdot p_n + 1 \end{align}

• By Lemma 1 we have that $N$ has a prime divisor. So there exists an integer $k$ with $1 \leq k \leq n$ such that $p_k$ is a divisor of $N$. But clearly $p_k$ also divides $p_1 \cdot p_2 \cdot ... \cdot p_n$. Fromt he equality above, we must also have that $p_k$ divides $1$. But this is impossible since $p_k \geq 2$.

• Therefore the assumption that there are only finitely many primes is false. So there must exist infinitely many primes. $\blacksquare$