Euclid's Theorem of the Existence of Infinitely Many Primes

Recall from the Prime and Composite Numbers page that an integer $p > 1$ is a prime number if the only divisors of $p$ are $\pm 1$ and $\pm p$, and an integer $p > 1$ that is not a prime number is called a composite number.

We will now look at a very famous, simple, and important theorem which states that there exists infinitely many primes.

Theorem 1 (Euclid's Theorem of the Existence of Infinitely Many Primes): There are infinitely many prime numbers.

• Proof: We will carry this proof out by contradiction. Suppose that instead there are a finite number of primes. Then we can list all of these primes:

(1)

\begin{align} \quad p_1, p_2, ..., p_k \end{align}

• Consider the number $n = p_1p_2...p_k + 1$. We have already see that every integer $n > 1$ has a prime divisor. Let this divisor be $p_i$ for some $i \in \{ 1, 2, ..., k \}$. Then $p_i \mid n$ and $p_i \mid p_1p_2...p_i...p_k$. But this implies that $p_i \mid 1$ which is a contradiction since all $p_i \geq 2$ and the only divisors of $1$ are $\pm 1$.

• Therefore the assumption that there were finitely many primes was false and so there are infinitely many primes. $\blacksquare$