This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American
Prime numbers are often described as the “atoms” of mathematics, or at least of numbers. A prime has exactly two distinct factors: itself and 1. (Hence 1 is not considered a prime number.) All whole numbers greater than 1 are either primes or products of primes.
One of the first questions a curious human could ask about prime numbers is how many there are, and one of the earliest proofs that there are infinitely many primes is a lovely argument from Euclid’s Elements.
Euclid’s proof starts with a finite list of prime numbers and describes a way to generate a prime that is not on the list. If your primes are p1, p2, p3,…,pn, take the product of all of them: p1×p2×p3×…×pn and add 1. This number, p1×p2×p3×…×pn +1, is not divisible by any of the primes on our list; the remainder when we divide it by one of those primes is 1. Hence, the finite list of primes is incomplete.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
A common misconception about this proof is that the number p1×p2×p3×…×pn +1 itself has to be prime. That is not necessarily the case. To see why, we can start thinking about what numbers we would get if we started with the first prime, 2, and used it to find new primes using the process from Euclid’s proof. The first one is easy: 2+1=3, and 3 is prime. To find the next number, we multiply 2×3 and add 1 to get 7, which is prime. To continue: 2×3×7+1=43, also prime. 2×3×7×43+1=1807, which is 13×139.
The Euclid-Mullin sequence is the sequence that starts 2, 3, 7, 43, 13, and so on: the first term is 2, and each subsequent term is the smallest prime factor of 1 plus the product of all previous terms. It is sequence A000945 in the Online Encyclopedia of Integer Sequences.
(Side question: Is the Euclid-Mullin sequence the poly-eponymous term in math with the greatest chronological gap between eponyms? Euclid, or the person or group of people who wrote Euclid’s Elements, lived around 300 BCE in Alexandria; American mathematician and engineer Albert Mullin was born in 1933 and died in 2017. If you know of a term named for people who lived more than 2200 or so years apart from each other, let me know on Twitter.)
Ken Ribet mentioned the Euclid-Mullin sequence when my cohost Kevin Knudson and I talked with him for our podcast My Favorite Theorem, and it’s been rattling around in my brain ever since. The sequence has infinitely many terms, but we know only 51 of them. As the number of terms grows, we run into very large numbers that take a long time to factor, in part because the sequence bounces around a lot. The seventh term is the number 5, but the ninth term has 14 digits! Finding the 52nd term of the sequence requires the factorization of a 335-digit number.
We do not know whether every prime number appears in the Euclid-Mullin sequence. The smallest prime not known to appear on the list is 41. The similar sequence that chooses the largest instead of smallest prime that divides 1 plus the product of the previous termsavoids an infinite number of primes. If the Euclid-Mullin sequence does avoid some primes, why? And could we look at a prime and tell whether it is in the sequence or not?
I am drawn to adorable and amusing math, so I hope the Euclid-Mullin sequence contains all prime numbers. I love the fact that it would give us a new natural order to put the prime numbers in. It would be like putting the letters of the alphabet in the alphabetical order of their phonetic spellings:
HRABDWEFXLMNSIJGKQOPCTVYUZ (phonetic spellings being somewhat debatable, your mileage may vary).
On the other hand, wouldn’t it be funny if somehow we could figure out that the sequence did not contain all prime numbers, but we couldn’t figure out which ones never showed up? The least amusing option, I suppose, would be for someone to figure out a simple rule that would determine whether a number was in the Euclid-Mullin sequence or not. But hey, the silver lining would be that we might actually gain some insight into prime numbers as a result!