Infinitude of primes
A Socratic walk-through of the infinitude of primes — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why can the prime numbers never run out?
Primes thin out as you climb. Between 1 and 100 there are 25 of them; between 9,900 and 10,000 there are 9. The gaps widen, and it is easy to imagine them widening until, somewhere far out, they stop appearing altogether. Nothing about the definition forbids that. So what would we have to show to rule it out — and could we do it without ever going out there to look?
Reasoning it through
REASONING #Start by asking what "running out" would mean. It would mean there is a complete list: finitely many primes, and every prime on it. Notice that this is a claim we can attack without knowing which primes are on the list or how long it is. Any finite list at all — that is the thing to argue against.
So take one. Call its members p1, p2, up to pk. What could we build from them that the list itself cannot account for?
Here is Euclid's move. Multiply them all together and add one. Call that number N. Now ask a small question about it: what happens when you divide N by any prime on the list? The product part divides cleanly by each of them, by construction. The added 1 does not. So every listed prime leaves remainder 1 when it divides N. Not one of them divides N.
Now the second ingredient, and it is the one people skip. Every whole number greater than 1 has a prime factor. Why? Look at its smallest divisor above 1. If that divisor had a factor of its own, strictly between 1 and itself, that factor would be a smaller divisor of the original number — contradicting the choice of smallest. So the smallest divisor above 1 has no such factors: it is prime.
Put the two together. N is greater than 1, so it has some prime factor q. But no prime on the list divides N. Therefore q is not on the list. The list was not complete after all.
And nothing about that argument depended on the list. Hand me any finite collection of primes and I will hand you back a prime you missed. A collection that can always be extended is not finite. That is the whole proof, and it is remarkable that it needs no computation at all — it fixes a property of every finite list rather than searching an infinite one.
Notice also what we did not conclude. We did not claim N is prime. Sometimes it is: 2 x 3 + 1 = 7. Often it is not. Take the first six primes: 2 x 3 x 5 x 7 x 11 x 13 + 1 = 30,031, which is 59 x 509. Both factors are primes, and neither is on the list we started from — exactly as the argument promised. The construction produces a number containing an unlisted prime, not an unlisted prime itself.
The analogy
THE ANALOGY #Think of a set of measuring rods, one for each prime, and a length you want to measure exactly. Lay every rod against the length N we built. Each one, no matter how many times you repeat it, always finishes one unit short of the mark. Yet N is not some unmeasurable quantity — it is a whole number, so some rod of whole length measures it. That rod is simply not in the set you were handed.
Rods invite you to picture measuring as a physical search, which suggests the missing rod must be found before the argument works; in fact we never find q, and the proof is complete without knowing a single thing about it beyond its existence.
Clarifying the model
THE MODEL #Three refinements are worth pinning down, because each is a place the argument is routinely misreported.
The first is the misstatement already flagged: "Euclid's number is prime." It is the single most common error about this proof, it is false, and 30,031 is the standard witness. What is true is weaker and sufficient: N has a prime factor, and that factor cannot be on the list.
The second: this is not essentially a proof by contradiction, though it is almost always dressed as one. Euclid's own version assumes nothing false. It takes a finite set of primes and constructs a new one — a procedure, not a refutation. The "suppose there are finitely many primes, derive a contradiction" packaging is a later convenience, and it is what makes people think the argument needs the impossible list to get started. It does not.
The third: none of this tells you where the primes are. Infinitude is a statement about not stopping, not about density or spacing. Both further facts are known and neither follows from Euclid. The gaps do get arbitrarily large — the run of numbers from n! + 2 to n! + n is composite all the way, and can be made as long as you like. And yet the primes remain thick enough that the sum of their reciprocals diverges, which Euler proved and which is a genuinely stronger statement than Euclid's, since a merely infinite set can have a convergent reciprocal sum, as the squares do.
One honest loose end: iterate Euclid's construction, always taking the new prime factor, and you get a sequence of primes — but which primes, and in what order, is not something the proof controls, and whether the closely related "Euclid numbers" contain infinitely many primes is an open question.
A picture of it
THE PICTURE #How to readStart at the rounded terminal at the top — it accepts any finite list, which is what makes the argument general. Follow down through the construction to the diamond, the only real question in the proof. The "yes" branch runs into the impossibility that no prime divides 1, so it is closed off; the "no" branch reaches the outcome, a prime the list omitted. The back-edge from that outcome to the start is the point: the machine never halts for lack of material.
What became clearer
WHAT CLEARED #The primes cannot run out because no finite list of them can survive one multiplication and one addition. The proof does not hunt for large primes, does not assume anything false, and does not claim the number it builds is prime — it only shows that the number's prime factor, whatever it is, was not on the list. Infinitude, here, is a fact about the failure of every finite list rather than a fact about the far reaches of the number line.
Where to go next
ONWARD #- Euler's proof via the divergence of the sum of reciprocals of primes, and why it says more than Euclid's.
- The prime number theorem: how the primes thin out, quantified.
- Furstenberg's proof, which reaches the same conclusion through topology.
Key terms
TERMS #| Term | What it means |
|---|---|
| Prime | a whole number greater than 1 whose only positive divisors are 1 and itself. |
| Euclid number | a number of the form (product of the first k primes) + 1. |
| Divergence (of a series) | the property of a sum growing without bound as more terms are added. |
Every term the collection defines is gathered in the glossary.