Famous Theorems of Mathematics/Euclid's proof of the infinitude of primes

From Wikibooks, open books for an open world
Jump to: navigation, search

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:

p1, p2, ... , pn

Now consider the number M defined as follows:

M = 1 + p1 * p2 * ... * pn

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

  1. It cannot be prime because pn is the biggest prime (by our initial assumption), and M is clearly bigger than pn. Thus, there must be some prime p that divides M.
  2. It is not divisible by any of the numbers p1, p2, ..., pn. Consider what would happen if you tried to divide M by any of the primes in the list p1, p2, ... , pn. 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 p1, ..., pn.

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 pn. 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 p1=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.