The Greek mathematician Euclid gave the following elegant proof that there are an infinite number of primes. It relies on the fact that all non-prime numbers --- composites --- have a unique factorization into primes.

Euclid's proof works by contradiction: we will assume that there are a finite number of primes, and show that we can derive a logically contradictory fact.

So here we go. First, we assume that that there are a finite number of primes:

- p
_{1}, p_{2}, ... , p_{n}

Now consider the number M defined as follows:

- M = 1 + p
_{1}* p_{2}* ... * p_{n}

There are two important --- and ultimately contradictory --- facts about the number M:

- It cannot be prime because p
_{n}is the biggest prime (by our initial assumption), and M is clearly bigger than p_{n}. Thus, there must be some prime p that divides M. - It is not divisible by any of the numbers p
_{1}, p_{2}, ..., p_{n}. Consider what would happen if you tried to divide M by any of the primes in the list p_{1}, p_{2}, ... , p_{n}. From the definition of M, you can tell that you would end up with a remainder of 1. That means that p --- the prime that divides M --- must be bigger than any of p_{1}, ..., p_{n}.

Thus, we have shown that M is divisible by a prime p that is not on the finite list of all prime. And so there must be an infinite number of primes.

These two facts imply that M must be divisible by a prime number bigger than p_{n}. Thus, there cannot be a biggest prime.

Note that this proof does not provide us with a direct way to generate arbitrarily large primes, although it always generates a number which is divisible by a new prime. Suppose we know only one prime: 2. So, our list of primes is simply p_{1}=2. Then, in the notation of the proof, M=1+2=3. We note that M is prime, so we add 3 to the list. Now, M = 1 +2 *3 = 7. Again, 7 is prime. So we add it to the list. Now, M = 1+2*3*7 = 43: again prime. Continuing in this way one more time, we calculate M = 1+2*3*7*43 = 1807 =13*139. So we see that M is not prime.

Viewed another way: note that while 1+2, 1+2*3, 1+2*3*5, 1+2*3*5*7, and 1+2*3*5*7*11 are prime, 1+2*3*5*7*11*13=30031=59*509 is not.