How Many Prime Numbers Are There?
Are there an infinite number of prime numbers? Or maybe there is a largest prime number, and every number after that is composite. To get a little insight into this, we might start listing the prime numbers, beginning 2, 3, 5, 7, 11, …, to see if any pattern emerges. About all that is readily apparent, however, is that the primes seem to “thin out” as we get into larger numbers. When we reach a few thousand, there are long stretches of consecutive numbers that contain no primes. This might make one speculate that there is some number after which the string of composite numbers is infinitely long (i.e., the second possibility above).
The Greek mathematician Euclid, who is usually associated with geometry, wondered about these questions about 300 BCE. He was able to prove that there are in fact an infinite number of primes, and his simple proof of this remains one the enduring classics of mathematical reasoning. The British mathematician G. H. Hardy (1877 – 1947) called the proof “… as fresh and significant as when it was discovered – two thousand years have not written a wrinkle on it”.
In this post I will describe Euclid’s proof.
First though, we need to understand a preliminary fact that will be used in the proof:
If two numbers A and B (with A larger than B) can each be evenly divided by a third number C, then C will also divide evenly into (A – B).
For example, the numbers 105 and 15 can each be divided evenly by 5. Therefore, 5 will also divide evenly into 105 – 15 = 90.
Now the proof: let’s suppose, says Euclid, that there are only a finite number of primes – call them A, B, C, D, …, E. Now compute the number N = (A x B x C x D x …E) + 1.
There are just two possibilities:
- N is a prime number. In this case, we have created a prime not among the original group, and we are done.
- N is a composite number. By definition then, N can be divided by at least one prime number, call it F. We will now show that F must be a “new” prime; that is, not in the original group A, B, C, D, …, E.To see why, suppose that F is one of the original set, say F = A. Obviously, F will divide into the product = (A x B x C x D x …E). By assumption, it will also divide into N. This implies, by the preliminary result described above, that F will divide into the difference: N – (A x B x C x D x …E). But this difference is just 1. Hence we have a contradiction; F was supposed to divide evenly into the difference, but it can’t, since the difference is only 1.The same result holds if we assume F = B, or F = C, etc. Therefore, F cannot be in the original group of primes – it is a new prime.
Thus, whether or not N is prime, we can always produce a “new” prime from a finite group of primes. Put another way, there is no limit to the number of primes that can be produced.
Euclid’s proof is an early example of a method called reductio ad absurdum (Latin: “reduction to the absurd”). We assume the opposite of what we want to prove, in this case, that there are a finite number of primes, then show that the assumption leads to a contradiction.
Hopefully, the ingenuity and insight in Euclid’s proof is apparent, and I think it is reasonable to say there is beauty in it. To be sure, this beauty is not accessible to everyone, just as not everyone can perceive beauty in Monet or Mozart. One of my goals in this blog is help a few more people come to see and enjoy mathematical beauty.
Note added July 10, 2012
In 1988, the magazine Mathematical Intelligencer asked a panel of mathematicians to vote on the “the most beautiful theorems in mathematics”. The results were tabulated into a list, and Euclid’s proof was number three on the list. I have written posts on some of the others on the list.