Euclid's 2,300-year-old proof that primes never run out

There is no largest prime number — and we have known this for about 2,300 years. The proof appears in Euclid's Elements, written around 300 BC [1], and it remains one of the shortest, cleanest arguments in all of mathematics: no computers, no heavy machinery, just one brilliant construction. In this paper we walk through it in full, flag the subtle detail that almost everyone gets wrong when retelling it, and then meet the twist: primes never run out, but they do fade.

Euclid's proof by contradiction

A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, ... Primes are the atoms of arithmetic — every whole number greater than 1 is a product of primes in exactly one way ($12 = 2 \times 2 \times 3$, and no other combination works).

The question is whether the supply ever dries up. Primes certainly get rarer as numbers grow — between 1 and 10 there are four, between 90 and 100 just one. Could there be a last prime?

Euclid answers with a proof by contradiction: assume the claim is false, follow the consequences honestly, and if we crash into an impossibility, the assumption must have been wrong.

Suppose, for contradiction, that there are only finitely many primes. Then we can write down the complete list of all of them:

$$p_1, \; p_2, \; p_3, \; \ldots, \; p_n$$

Now build a new number by multiplying the entire list together and adding 1:

$$N = p_1 \times p_2 \times p_3 \times \cdots \times p_n + 1$$

Divide $N$ by any prime on our list and it leaves remainder 1 — because $N$ is exactly one more than a multiple of each of them. So no prime on the list divides $N$.

But every whole number greater than 1 has at least one prime factor. So $N$ has a prime factor — and that prime cannot be any of $p_1, \ldots, p_n$. Our list, which was supposed to contain every prime, is missing one. Contradiction. The assumption was false, and the primes never end. $\blacksquare$

The proof is often misquoted as: "multiply the primes together, add 1, and you get a new prime." Not so — the proof only shows that $N$ has a prime factor outside the list, which is all the contradiction needs. And the misstatement genuinely fails. The pattern starts out looking prime-like ($2+1=3$, $2 \times 3 + 1 = 7$, $2 \times 3 \times 5 + 1 = 31$, then 211, then 2,311 — all prime), but multiply the first six primes and add 1:

$$2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30{,}031 = 59 \times 509$$

Not prime. But look at its factors: 59 and 509 are both prime, and neither is on the list 2, 3, 5, 7, 11, 13 — which is exactly what Euclid promised. The construction never guarantees a prime; it guarantees evidence of a missing prime, and that is enough.

Infinite, but fading

So primes go on forever — yet they thin out as we travel along the number line. Write $\pi(x)$ for the number of primes up to $x$ (nothing to do with the circle constant), and watch the density fall:

The prime number theorem, proved in 1896, pins down the fade precisely [2]:

$$\pi(x) \approx \frac{x}{\ln x}$$

where $\ln$ is the natural logarithm. The estimate for one million is $\frac{10^6}{\ln 10^6} \approx 72{,}382$, against a true count of $78{,}498$ — about 8% low, and the relative error keeps shrinking as $x$ grows. Primes behave like a resource that never runs out but gets steadily harder to mine: near $x$, roughly one number in every $\ln x$ is prime.

What remains unproven

Euclid's argument still stands after 2,300 years: the primes never run out, because any finite list of them can be used to manufacture evidence of a prime it missed. Yet the supply thins forever, at the exact rate $\frac{x}{\ln x}$. And astonishingly, basic questions remain open. Twin primes — pairs like 11 and 13, or 101 and 103, just two apart — seem to keep appearing forever, but whether they truly never end is still unproven. Infinity, as we explore in How big is infinity?, is where mathematics gets strange — and where even simple-sounding questions, like the Collatz conjecture, can resist every assault for centuries.

---

References:

[1] Euclid, Elements, Book IX, Proposition 20. Translation: Thomas L. Heath, The Thirteen Books of Euclid's Elements, Vol. 2 (Dover Publications, New York, 1956).

[2] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed. (Oxford University Press, Oxford, 2008).

Note: All counts and factorisations in this paper (including 30,031 = 59 × 509 and the 78,498 primes below one million) were verified computationally. Euclid's original statement — "prime numbers are more than any assigned multitude of prime numbers" — was phrased geometrically; the algebraic version here is its standard modern form.