Euclid created this simple and beautiful proof of infinite prime numbers. I am writing this down as I understand it to make it more solid in my own mind. Caveat: I am not a mathematician and don’t use rigorous terms below.

Let S be the set of all prime numbers. Multiply all members of S to come up with a number N. N is not prime (being composed of all primes in S). But N+1 may be prime; if so, N+1 can be added to S.

If N+1 is not prime, then there exists a prime number q which is less than N+1 and which evenly divides N+1 and which is not in S (since no number in S evenly divides N+1 because there will always be a remainder 1). Therefore q can be added to S.

Example 1: Let’s assume the set of known prime numbers includes only 1, 2, 3, 5, and 7. This is the set S. If we multiply these numbers together (1 * 2 * 3 * 5 * 7) we get 210. This is N. We know N is not prime because it is composed of all S. N+1 = 211. We can check to see if 211 is prime through factorization. It turns out that 211 is prime so we have just found a new prime number.

Example 2: Let’s try a larger S that includes 11 and 13 so that N = 30,030 and N+1 = 30,031. 30,031 is not prime because we find two numbers 59 and 509 (these are q in the proof) that evenly divide N+1 but which are not in S.

The first part of the proof (If N+1 is prime, then we found another one) is pretty obvious, but the second part is where the cleverness is: if N+1 is not prime, then there must be another prime number somewhere between our last known prime in S and N+1 that evenly divides N+1. Why? Because we know that nothing in S evenly divides it (we added 1 to N, so there will always be at least remainder 1), therefore whatever number that does evenly divide it must be a new prime not in S.

“Spirale Ulam 150” by Généré avec la librairie GD de PHP, par Cortexd. Licensed under Public Domain via Commons - https://commons.wikimedia.org/wiki/File:Spirale_Ulam_150.jpg#/media/File:Spirale_Ulam_150.jpg

Last modified on 2015-07-29