There is no last prime

The primes thin out. Below a hundred there are twenty-five of them; between nine hundred and a thousand there are fourteen; between a million and a million and a hundred, six. A reader watching that trend and expecting it to reach zero somewhere would be making an entirely reasonable extrapolation from the evidence, and would be wrong.

That is Euclid’s argument, from Book IX of the Elements, and it is about as old as the sieve. It is one of a small number of proofs that have been in continuous use for twenty-three centuries without anybody improving on them.

The picture is the whole of it. The product $2 \times 3 \times 5 \times 7 = 210$ is divisible by each of its factors — that is what a product is — so each of them tiles it with nothing left over. Adding one leaves each of them with a remainder of exactly one. So $211$ is divisible by none of $2, 3, 5, 7$; and since every number above one has at least one prime factor, $211$’s prime factors are not on the list.

Any finite list of primes therefore fails to be all of them. There is no last prime.

What the argument does not say #

Euclid’s proof is regularly described, in textbooks and in conversation, as a machine for producing new primes: take the primes so far, multiply, add one, and out comes a prime. It says nothing of the sort, and the difference matters.

$30{,}031$ is composite, and it is the first case where this happens. The products $3$, $7$, $31$, $211$ and $2311$ are all prime; the sixth is not. Anybody testing the “machine” by hand would have checked five cases, found five primes, and formed a confident and false general belief — which is exactly the failure mode this collection keeps running into, and the reason a handful of small cases is not a sample of the cases.

What the argument actually establishes is weaker and quite sufficient: the constructed number has some prime factor, and that factor is not on the list. Whether the constructed number is itself prime is a separate question that Euclid never asks, and the proof does not become shaky when the answer is no.

That cube is the reason the construction works so cleanly. Every divisor of a primorial above one contains at least one of the listed primes, so every divisor above one is caught by the remainder argument. Adding one steps off the lattice entirely — the result shares no factor with any corner of it — and the only place its prime factors can live is outside the list. The picture makes “coprime to the product” and “coprime to every factor at once” the same statement, which is exactly the step the proof turns on.

There is a small warning attached. A larger list makes a larger cube, and the cube’s corners are the numbers the argument rules out; they are not the numbers between the primes. The construction never claims to have found the next prime, and in the six-prime case the new primes it finds, $59$ and $509$, sit far below the number that produced them.

The distinction is between an existence proof and a construction, and it recurs everywhere. The pigeonhole principle proves that two things share a box without saying which two. Euclid’s argument proves that a new prime exists without saying what it is. Both are complete proofs; neither hands over an object.

The contradiction that is not needed #

Euclid’s version is sometimes given as a proof by contradiction: suppose the primes are finite, form their product, add one, and derive an absurdity. It reads well and it is not what Book IX says.

The original is a direct statement. Given any three primes, a fourth exists that is none of them. No supposition, no contradiction, no infinite set anywhere in the argument — the proposition is about extending a finite list, and Euclid states it that way because the Greek mathematical vocabulary had no comfortable way to speak of a completed infinity.

That turns out to be the better version. It is constructive in the logician’s sense: it takes a finite list of primes and produces a number that must contain a new one, and running the process gives an explicit, if absurdly inefficient, way to generate primes forever. The proof-by-contradiction dressing adds nothing and obscures that.

Modern practice has drifted back towards Euclid. Where the two forms are equally available, the direct one is preferred — not out of foundational scruples but because a direct proof gives an algorithm and a contradiction gives only a fact.

Other proofs, and what each one costs #

The result is important enough to have been proved many times over, and comparing the proofs says more about the subject than any of them says alone.

Euler’s, from around 1737, is analytic. If there were finitely many primes, the product

$$\prod_p \left(1 - \frac{1}{p}\right)^{-1}$$

would be a finite product of finite numbers, hence finite. Expanding each factor as a geometric series and multiplying out gives every reciprocal $1/n$ exactly once — by unique factorisation — so the product equals $\sum 1/n$, and the harmonic series diverges. A finite product cannot equal an infinite sum, so there are infinitely many primes.

This is a great deal more machinery for the same conclusion, and it repays the cost immediately. Euler’s argument does not merely show there are infinitely many primes; it shows that $\sum 1/p$ itself diverges, so the primes are substantially infinite — much commoner than the squares, whose reciprocals converge. Euclid’s argument cannot see the difference.

The gap between those two claims is the gap between the two eras of the subject. For two thousand years the primes were an object of exact, finite reasoning: an argument either produced a new prime or it did not. Euler’s identity brings a limit into a question about divisibility and gets an answer nobody could have reached by counting, and everything afterwards — the prime number theorem, the zeta function, the Riemann hypothesis — is downstream of that single move. The whole apparatus exists because somebody was willing to write down an infinite product of things that have no business being multiplied together.

Goldbach’s needs no analysis at all. The Fermat numbers $F_n = 2^{2^n} + 1$ satisfy $F_0 F_1 \cdots F_{n-1} = F_n - 2$, so any common factor of two of them divides $2$ — and they are all odd. Infinitely many pairwise coprime numbers means infinitely many primes.

Fürstenberg’s, from 1955, is topological: put a topology on the integers in which arithmetic progressions are open, observe that each is also closed, and note that the complement of the union of the progressions $p\mathbb{Z}$ is $\{-1, 1\}$, which is not open. If there were finitely many primes, that union would be closed and its complement open. It is a genuine argument and it is Euclid’s argument in a costume — the topology is a way of saying “coprime” — but it is a good illustration of how far a statement can be moved before it stops working.

Counting squarefree numbers, and how weak Euclid’s bound is #

A qualitative proof can usually be squeezed for a quantitative statement, and squeezing these two is the fastest way to see how far apart they are.

Euclid’s, squeezed. The construction says the next prime is at most the product of the ones before it, plus one. Running that as a recursion from the start gives a bound on the $n$-th prime of $2$ raised to the power $2^{n-1}$ — a tower that doubles its exponent at every step. Turned round, it says the count of primes below $x$ grows at least like the logarithm of the logarithm of $x$.

That is a genuine theorem and it is comically weak. It guarantees perhaps ten primes below a number with a hundred digits. Nothing is wrong with the proof; the bound is loose because the construction throws away the primes it does not use, and it throws away almost all of them.

Erdős’s proof, from 1938, is a counting argument and does far better. Every whole number splits uniquely as a square times a squarefree number. Suppose the primes up to $N$ are $k$ in total. A squarefree number below $N$ is a product of some subset of those $k$ primes, so there are at most $2^k$ of them; a square below $N$ has a root below the square root of $N$, so there are at most $\sqrt{N}$ of those. Every number up to $N$ is one of each, so

$$N \le 2^k \sqrt{N},$$

which rearranges to say that $2^k$ is at least $\sqrt{N}$ — so the number of primes below $N$ is at least half the base-two logarithm of $N$.

That is a logarithm rather than a logarithm of a logarithm, and the gap between the two is the difference between a bound that is useless at any size and one that is merely loose. Below a million it guarantees ten primes; the truth is 78,498. Below $10^{100}$ it guarantees a hundred and sixty-odd, which is still nothing like the truth and is a great deal more than Euclid’s ten.

And the method is the one this collection keeps meeting. Nothing in Erdős’s argument is about primes as such: it counts one set of objects two ways, gets an inequality, and reads a conclusion off the inequality. It never constructs a prime, never assumes finiteness for contradiction, and never touches an infinite series. What it uses is unique factorisation and the observation that a subset of $k$ things has $2^k$ choices, which is the counting the divisor cube above draws.

So the proofs sit on a scale of what they buy. Euclid’s produces a prime and a bound too weak to use. Erdős’s produces no prime and a bound worth having. Euler’s produces neither and shows the primes are dense enough that their reciprocals diverge. Each pays more machinery for a stronger statement, and the qualitative conclusion — that the list never ends — is the cheapest thing any of them says.

What the picture cannot show #

The bars in the first figure make the argument visible and hide its scale entirely. The product of the primes up to $n$ — the primorial — grows roughly like $e^n$, so the numbers the construction produces get large immediately. The primorial of the primes up to $100$ has $37$ digits; the primorial up to $1000$ has $416$.

So the construction proves that primes keep arriving and gives no useful information about where. It says a prime exists somewhere between $p_k$ and $p_1 p_2 \cdots p_k + 1$, which is an interval of astronomical width. Bertrand’s postulate — proved by Chebyshev in 1852 — says something far stronger, that a prime always lies between $n$ and $2n$, and it takes real work.

The figure also cannot show the thing the whole subject wants, which is regularity. The primes below a hundred can be drawn; the primes near $10^{40}$ cannot be drawn, counted, or reasoned about individually, and the statements known about them are all statements about density. This is the same limitation the sieve’s staircase runs into: a picture of the beginning of the number line is a picture of the least representative part of it.

Where the gaps come from #

There is one more thing the construction gives away, and it comes from reading the same picture backwards.

The numbers $n! + 2, n! + 3, \ldots, n! + n$ are each divisible by $2, 3, \ldots, n$ respectively, because $n!$ contains every one of those factors and the added term supplies the rest. So they are all composite, and there is a run of $n - 1$ consecutive composite numbers sitting somewhere near $n!$.

That is the same move as Euclid’s — build a number that every small prime divides, then step away from it by one — used to produce absence rather than presence. Adding one to the primorial escapes every small prime at once; adding $k$ to the factorial lands inside one of them deliberately. Gaps of every size exist, and the construction that shows it is the construction that shows there is no last prime, run in reverse.

The two results sit oddly together. Euclid’s says the primes never run out; the factorial construction says they can be absent for as long as one likes. Both are elementary, both are constructive, and together they leave the actual behaviour completely open — a run of a million composites exists somewhere, and so does a prime after it. Between those two statements is where the entire modern subject lives, and neither of the arguments that produced them can say anything about the space between.

The shape of the argument #

Strip the arithmetic away and what remains is a general move worth naming: to show a collection is not everything, build something that differs from each of its members in a way each member can detect.

Every prime on the list detects $210 + 1$ as not-its-multiple. That is precisely the structure of Cantor’s diagonal argument, which shows there are more real numbers than boxes to put them in by building a number differing from the $n$-th in the $n$-th place. The two proofs are separated by two thousand years and are recognisably the same idea: a candidate for completeness is defeated by an object constructed to disagree with every entry.

Euclid’s version has the advantage that the disagreement is arithmetic — a remainder of one — and can therefore be drawn. That is why the picture at the top of this essay is a picture of blocks and one leftover square, and why it carries the whole proof.

The same shape turns up a third time in a place with no numbers in it at all. To show that a list of essays does not cover a subject, write one that differs from each listed essay in a point that essay is about; to show that a set of axioms does not settle everything, build a statement that disagrees with each provable one. Gödel’s construction is the diagonal argument again, and its ancestry runs back through Cantor to the leftover square. What all three have in common is that the constructed object is specified by its disagreements rather than described directly — nobody has to know what $211$ factors into, only what it is not divisible by.

That is also why these arguments feel unsatisfying on first meeting. They end without producing the thing they are about, and the reader is left holding a certificate rather than an object. In this case the certificate is worth more than the object would be: one more prime is one more prime, and knowing that the list can never be finished is a fact about all of them at once.

The largest one anybody has written down #

There being no last prime does not stop people from keeping a record of the largest one found, and the record has an unusual property: for almost the whole of the modern era it has been held by a number of one particular shape.

The reason is a test rather than a coincidence. Deciding whether an arbitrary $n$ is prime is expensive; deciding whether $2^k - 1$ is prime has a special method, the Lucas–Lehmer test, which is fast enough that numbers with tens of millions of digits are within reach. Nothing similar exists for numbers in general, so the record goes to the shape that has the test.

That is worth sitting with. The largest known prime is not the largest prime anybody has looked near; it is the largest one in the only family that can be checked at that size. Whether infinitely many Mersenne numbers are prime is unknown, and it is one of the older open questions in the subject — a search that has run since Mersenne’s list of 1644, has found fifty-odd examples, and has never been able to say whether the fifty-first exists.

The same shape appears in the numbers that are the sum of their own parts, where the Mersenne primes turn out to generate every even perfect number and nothing else. Two questions that sound unrelated — how large a prime can be certified, and which numbers equal the sum of their divisors — turn out to be the same question, and the reason is the rectangle in the figure above.

Where the ladder goes next #

The argument leans, quietly, on a fact used without comment: every number above one has a prime factor, and the factors of $30{,}031$ are what they are and not something else. That is unique factorisation, and it is worth proving rather than assuming.

The other direction is the one Euler opened. Knowing that the primes never stop is the beginning of asking how often they arrive, which is the sieve’s density question and eventually the prime number theorem. And the same style of argument — assume a solution, build a smaller one, and note that the process cannot continue — is what makes a square that cannot shrink impossible, which is the other classical proof everybody meets early and nobody forgets.