It's not as neat as Furstenberg's proof that ariels demonstrated, but much more intuitive. First proved by Euclid and some say the first example of a proof by reductio ad absurdum


Assume there are finitely many prime numbers, thus you can list them. Multiply together all the numbers in this list and then add one to the total. The number you have created by this process has a remainder of one when divided by any of these numbers that you just claimed were the only primes there are.

Clearly, either this number is prime or its prime factorization contains primes that this so-called list of ALL primes missed! So we make a new list with these primes, and repeat the process, and that list will be incomplete as well. It becomes clear that it is impossible to make a list of all the primes, so the assumption that there are finitely many primes must be false.

Also, a necessary consequence of this is that there is no largest prime number. If you think a number N is the largest prime number, take the primorial of that number, N#, which is the product of all primes less than or equal to that one. N#+1 will have a remainder of one when divided by any of the primes less than or equal to N, so it must contain primes larger than N in its prime factorization.

A common misunderstanding of this proof is that N#+1 will always be prime, but in fact, only in special cases is N#+1 prime itself. Such numbers are rare numbers called primorial plus one primes.