Proof of Infinitely Many Primes
Already 300 BC Euclid was able to proof in his Elements that there are infinitely many primes. We can proof it as follows:
Let’s assume only limited number of primes \(p_1, \dots, p_n\) exist. Then, there is a number \(m\) which can be written as the product of these prime numbers.
\[m=p_1\cdot p_2\cdot\ \ldots\ \cdot p_n\]If we add the number 1 to this number we have two options:
Either \(m+1\) is a prime number. This would contradict our assumption and therefore our assumption would be wrong and there must be an infinitely number of primes.
Or \(m+1\) is no prime number. Then, there must be some \(p_i\) which divides \(m\) and \(m+1\). That would mean (see here) that \(p_i\) also divides the difference \((m+1)-m=1\). That would mean that \(p_i\) must divide \(1\) which is not possible as \(p_i\) is prime and therefore greater than \(1\). Again, our assumption must be wrong and there must be an infinitely number of primes.