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