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