# 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$$