there are infinitely many prime numbers

I really like the #paperswelove thing that seems to be happening all around.

Instead of discussing a complete paper, I gonna start writing about Theorems I love – and why not start with this real gem:

there are infinitely many prime numbers

I guess you all know what a prime number is: a natural number \(n\) is called prime if it is divided only by \(1\) and itself.

So the task of the proof is clear: we have to show that set of primes is not finite.

There are several proofs, but I will show you Euclid’s, because IMO it has the merit of being both basic and very beautiful.

The idea is, that given a finite set of primes, we can always find another one not in this set. Then surely no finite set suffices and the theorem follows.

Now how can we show this in such a general setting?

It turns out that it’s really not too hard (most students have no problem finding the proof) once we just named and listed things:

Say \(P = \{ p_1,p_2,…,p_n \} \) is a finite set of primes (note that we can enumerate them in this case), and look at the number:

$$ m = \prod_{i=1}^n p_i + 1$$

What can we say about \(m\)?

Well it either is a prime or it is not – if it is a prime than surely it was not in the set itself (as it’s greater than all the primes there – remember we are dealing with natural number \(\geq 1\) ). As \(m\) was not in \(P\) and is a prime we have found what we where looking for!

If \(m\) was not prime itself than it surely has a prime factor, as every number greater one has (that is another beautiful theorem – maybe I should write about it soon). But none of the primes \(p_i\) can be this factor!

Why is that?

Well because we know that the reminder of \(m\) divided by any one of the \(p_j\) is \(1\):

$$ m \ mod \ p_j = \prod_{i=1}^n p_i + 1 \ mod \ p_j $$

but of course each \(p_j\) divides the product of all the \(p_i\)’s – so

$$ \prod_{i=1}^n p_i \ mod \ p_j = 0 $$ and $$ m \ mod \ p_j = 0 + 1 \ mod \ p_j = 1$$

So we have shown that none of the primes \(M\) can be a prime-factor of \(m\), so there must be another prime not in \(M\) and we are done as well..

That’s it! (QED 😀 )