The Infinity of the Primes

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$