Euclid’s Elements, Book IX, Proposition 20.

**Theorem :**

Prime numbers are more than any assigned multitude of prime numbers.

That is, there are infinitely many primes.

**Proof :**

Suppose that there are \(n\) primes :

\(p_1, p_2, …, p_n \)

Let \(m\) be their product :

\(m = p_1 \cdot p_2\cdot … \cdot p_n\)

Now consider the number \(m + 1\) :

i) If \(m + 1\) is prime, then there are at least \(n + 1\) primes.

For example :

\(2 \cdot 3 \cdot 5 = 30\) and \(31\) is prime.

ii) If \(m + 1\) is not prime, then some prime \(q\) divides it. In this case, \(q\) cannot be any of the primes \(p_1, p_2, …, p_n\) since they all divide \(m\) and do not divide \(m + 1\). Therefore, there are at least \(n + 1\) primes.

For example :

\(2 \cdot 7 \cdot 11 = 154\) and \(155 = 5 \cdot 31\)

This proof is over \(2,000\) years old.

■

Notes :

The fundamental theorem of arithmetic states that every positive integer greater than \(1\) is represented by a unique factorisation of prime numbers.

One is neither prime nor composite.

© OldTrout \(2020\)