Famous Theorems of Mathematics/Euclid's proof of the infinitude of primes
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:
- 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.
- 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.