The Infinity of the Primes

OldTrout, Going Postal

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 \(2019\)
 

No Audio file – Does not translate well