Infinite Primes Proof (Euclid's Proof)

We will prove there are infinitely many primes by contradiction. This proof is by Euclid, and is one of the earliest known proofs:

Assume that there is a finite number of prime numbers. We can, therefore, list them like so:

\[p_1, \hspace{1mm} p_2, \hspace{1mm} p_3,\ldots,p_n\]

Now consider the number:

\[N=(p_1\times p_2\times p_3 \times \cdots \times p_n)+1\]

Notice that when you divide N by any of the primes that we listed, the remainder will be 1. Therefore either N itself is prime, or its prime factorisation contains only primes that were not on our list.

This contradicts the assumption that our list contained all primes, and therefore there must be an infinite number of primes.

(0 Votes)