Appendix 2
Infinitely Many Primes
Galway had come across Euclid’s proof that there are infinitely many prime numbers. Here’s a short primer on primes followed by the proof.
Some positive integers can be decomposed into a product of two smaller ones; 28 (= 4 × 7) and 315 (= 9 × 35) are examples of such composite numbers. Those that can’t be so decomposed are called prime. Put another way: a positive integer p > 1 is prime if its only (positive) divisors are itself and 1, so that it can only be decomposed in the trivial way p = 1 × p. Prime numbers are the “blocks” from which all numbers can be built, in the sense that every positive integer greater than 1 is a product of primes (or it is itself a prime)—and it is therefore divisible by some prime. For example, 4,095 = 3 × 3 × 5 × 7 × 13, so 4,095 is divisible by the primes 3, 5, 7, and 13.
The first ten prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. Does the list of primes eventually stop or does it go on forever? In other words, is the set of all prime numbers finite or infinite? Euclid answered this question in the Elements. He stated the theorem that there are infinitely many primes without using the term “infinity”: “Prime numbers are more than any given multitude of prime numbers” (Book IX, Proposition 20). His proof is short and beautifully simple. Here it is, essentially unchanged, in modern notation:
Consider the list of primes up to a certain prime P. If we multiply together all the numbers on the list and add 1 to the result, we obtain a number N = (2 × 3 × 5 × . . . × P) + 1 greater than all those on the list. Now, either N is prime or it isn’t. If N is prime, then the list of primes doesn’t stop at P. On the other hand, if N is not prime, then it’s divisible by some prime, say H. But H must be different from all the primes on the list because none of these divides N (the remainder of such a division is always 1). Thus, in either case we have found a prime not on the list, so the sequence of primes never stops; in other words, there are infinitely many primes.
In September 2006, using a computer program, it was discovered that the number 232,582,657 – 1 is prime, and at the time it was the largest known prime. This is an extremely large number; if written down, its nearly 10 million digits would stretch for almost 20 kilometers. Some 2,300 years ago and without the help of any computer, Euclid knew that such large prime numbers—and even larger ones—existed: he had proved it. Such is the power of mathematical proofs.