Cobra Effect · Maths and proof
The primes never run out
How a proof over two thousand years old shows the primes never run out.
7 cards, read aloud in 2:37, with a test and sources.
Some numbers cannot be split into equal groups at all.
Twelve can be split into twos, threes, fours or sixes. But seven can only be split into sevens, or into ones. Numbers like seven, divisible only by one and by themselves, are called primes. Every other whole number above one can be made by multiplying primes together.
As numbers get bigger, primes become rarer.
Among the first ten numbers there are four primes, but they thin out further along. So a natural question arises. Do the primes eventually stop, or do they go on without end?
More than two thousand years ago, Euclid answered that question.
His great book, the Elements, gathered and proved results about shapes and numbers. One of its proofs shows that the primes never run out. In an English translation, he says the primes are more than any assigned multitude of primes.
His argument starts with any list of primes you like.
Take the primes on the list, and find the smallest number they all divide into exactly. Then add one. Each prime on the list divides the first number exactly, so it cannot divide a number that is one more.
That new number either is a prime, or has a prime factor that is not on the list.
Either way, a prime is missing from the list. Whatever list you start with, you can always find one more. So no list of primes can ever be complete.
The new number is not always prime itself.
Multiplying two, three, five, seven, eleven and thirteen, then adding one, gives 30,031. That number is not prime. It is fifty nine times five hundred and nine. But fifty nine and five hundred and nine are both primes that were missing from the list. And despite how it is often retold, Euclid’s proof does not argue by contradiction. It simply builds a new prime.
So when a question asks whether something ever ends, look for a way to always make one more.
Euclid did not count the primes. He showed a method that beats any list anyone could ever write. A single clever step can settle a question about endlessly many cases.
Sources
- Euclid’s Elements, Book IX, Proposition 20, David Joyce, Clark University. The proof itself, with commentary.
- Prime Simplicity, The Mathematical Intelligencer, 2009. Why Euclid’s proof is so often misdescribed.
- Euclid of Alexandria, MacTutor History of Mathematics. What is known of Euclid and his Elements.
Nearby ideas
- The long journey of zero. How zero grew from a gap in a number into a number in its own right.
- Seven bridges and a walk that could not be done. How Euler proved a walk impossible without trying a single route.
- Some infinities are bigger than others. How Georg Cantor showed that some infinities are larger than others.
- The limits of proof. How Kurt Godel found limits that no system of proof can escape.
- The margin that was too small. How Andrew Wiles proved Fermat's three hundred year old claim.