Kalyan Kaushik Khasibhatla Software Engineer
Search the writing

Mathematics Essay 5 min read

Euclid's list that can't be finished

The proof that there are infinitely many primes doesn't construct a new prime — it constructs a number guaranteed to have a prime factor missing from any finite list. That distinction is the whole proof.

I’ve known “there are infinitely many primes, Euclid proved it” since school, in the same way I knew E=mc2E=mc^2 — as a fact to cite, not a thing to reconstruct. Actually rebuilding the proof turned out to hinge on a distinction I’d never noticed: it doesn’t produce a new prime. It produces a number that’s guaranteed to have a prime factor you didn’t already have, which is a strictly weaker and much more clever claim.

The simple version

Imagine you have a bag of special “building block” numbers (primes) and you’re sure you’ve found every single one. Multiply them all together and add one more — now try to rebuild that new number out of only the blocks in your bag. It never divides evenly; there’s always a leftover block missing from your bag. That leftover proves your bag was never complete, no matter how big it was.

Why primes are worth this much attention

Definition(Prime)

An integer p>1p > 1 whose only positive divisors are 11 and pp itself.

Theorem(Fundamental theorem of arithmetic)

Every integer n>1n > 1 can be written as a product of primes, and that factorisation is unique up to the order of the factors.

I’m stating this without proof — it’s a post of its own — but it’s the reason primes get called the atoms of the integers: multiplicatively, everything is built from them, and the recipe is unique. That’s what makes “how many are there” a question worth three pages instead of one.

The claim, and the proof’s actual shape

Theorem(Infinitude of primes (Euclid, Elements IX.20))

There is no largest prime — equivalently, the set of primes is infinite.

Proof

Suppose, for contradiction, that there are only finitely many primes: p1,p2,…,pnp_1, p_2, \ldots, p_n. Form the number

N=p1p2⋯pn+1.N = p_1 p_2 \cdots p_n + 1.

NN is larger than every pip_i, so if it’s prime, it’s a prime not in the list — contradiction already. If it’s not prime, the fundamental theorem of arithmetic says it has some prime factor qq. Check qq against the list: for every pip_i, dividing NN by pip_i leaves remainder 11, since NN was built as “a multiple of pip_i, plus one.” So pi∤Np_i \nmid N for every ii — meaning qq, whatever it is, cannot be any pip_i. Either way, a prime outside the assumed-complete list exists, contradicting the assumption that p1,…,pnp_1, \ldots, p_n was all of them.

The proof structure is worth sitting with: it’s not “here is a formula that generates primes.” It’s “any finite list of primes is provably incomplete,” which is a much easier thing to establish — you never have to say what the missing prime is, only that the current list can’t contain it.

The trap: NN itself usually isn’t prime

This is the part I’d genuinely misremembered. Take the first few primes and check:

2⋅3⋅5⋅7⋅11⋅13+1=30031=59×509.2\cdot3\cdot5\cdot7\cdot11\cdot13 + 1 = 30031 = 59 \times 509.

3003130031 is not prime — but the proof never claimed it would be. It claimed 3003130031‘s prime factors, 5959 and 509509, aren’t in {2,3,5,7,11,13}\{2,3,5,7,11,13\}, which is true and is all the proof needs. “Multiply the known primes and add one” is not a prime-generating machine; it’s a machine for manufacturing a witness that the list was incomplete. Conflating the two is a common misreading, and I’d been making it for years without noticing.

A second proof, for the contrast

Euler’s proof is a completely different kind of argument and worth having side by side, because it previews the next post in this series — density, not just infinitude.

Theorem(Euler's proof sketch)

If the primes were finite, the product ∏p(1−1p)−1\prod_p \left(1 - \tfrac{1}{p}\right)^{-1} over all of them would be a finite number. But that product equals ∑n=1∞1n\sum_{n=1}^{\infty} \tfrac{1}{n} by unique factorisation (expanding each factor as a geometric series and multiplying out generates every positive integer’s reciprocal exactly once) — and the harmonic series diverges. A finite product can’t equal a divergent sum, so the prime list can’t be finite.

Euclid’s proof is combinatorial and constructive-ish — it hands you a specific witness number for any finite list you propose. Euler’s is analytic and gives no witness at all, only a contradiction between a finite quantity and something that provably grows without bound. Same conclusion, and the fact that two structurally unrelated arguments both land on it is part of why the result feels so solid.

What I’d forgotten

That the proof is a statement about any finite list, universally quantified, not a statement about the sequence of primes in order. It works identically whether the assumed list is {2,3,5}\{2,3,5\} or the first ten trillion primes — nothing about the argument depends on which finite set you started with, which is exactly what “infinite” is supposed to mean and I’d never actually connected the two.

What I’d check

I asserted the geometric-series expansion in Euler’s sketch “generates every positive integer’s reciprocal exactly once” and waved at unique factorisation to justify it. That deserves an actual line of algebra — multiplying out ∏p(1+p−1+p−2+⋯ )\prod_p (1 + p^{-1} + p^{-2} + \cdots) and checking that the coefficient of n−1n^{-1} in the result is exactly 11 for every nn — rather than the hand-wave I gave it here.

Quick recap (quiz yourself)

Q: What is a prime number? A: A whole number greater than 1 whose only divisors are 1 and itself.

Q: In Euclid’s proof, what number do you build from an assumed-complete list of primes? A: N=N = (the product of every prime in the list) +1+ 1.

Q: Why can’t any prime from the original list divide NN? A: Because dividing NN by any of them leaves a remainder of 1, by construction.

Q: Does Euclid’s proof show that NN itself is always prime? A: No — NN often isn’t prime; the proof only shows NN‘s prime factors (whatever they are) can’t be in the original list.

Q: What does Euler’s proof use instead of a constructed number? A: A contradiction between a supposedly finite product and the harmonic series, which is known to diverge.