Now Obvious
№ 13 · mathematics

Why there is no largest prime

A prime is a whole number bigger than 1 that nothing divides except 1 and itself. There is no biggest one. Whatever list of primes you hold, there is always a prime missing from it.

Why it matters

Every whole number breaks into primes in exactly one way, so primes are the atoms of arithmetic. If the supply ran out, number theory would be a finite subject. It does not run out, and the argument that shows this is one of the oldest surviving proofs in mathematics — Euclid wrote it down around 300 BC. It is also the template for a whole style of reasoning: assume you are finished, then build the thing that shows you were not.

The mechanism

Take any finite list of primes. Multiply them all together, then add 1. Call the result N.

Now divide N by any prime on your list. The product part divides cleanly, and the extra 1 is left over as the remainder. So no prime on the list divides N.

But every whole number bigger than 1 has at least one prime factor — either it is prime itself, or it splits into smaller factors, which split again until only primes are left. So N has a prime factor. That factor is not on your list. Your list was incomplete.

Notice what the argument does not say. It does not say N is prime. Multiply 2, 3, 5, 7, 11 and 13, add 1, and you get 30031, which is 59 × 509. Neither 59 nor 509 was on the list, and that is all the proof needs.

Interactive Tap primes to build your list, then add the prime your list just proved it was missing.

rounds: 0
your list—
product + 1 = N—
N ÷ each prime—
prime factors of N—
verdict—
N is the product plus one. Every listed prime leaves remainder 1, so none of them divides N — and N’s own prime factors (in red) are never on the list. Try to build a list that closes the gap. You cannot. Or let the machine try: each round adds the prime it just found, and the next round finds another. The list grows without end.

In one breath

Any finite list of primes can be used to build a number that none of them divide. That number has a prime factor, so a prime was missing. Since this works for every list, no list is complete, and the primes go on forever.

Where this comes from

  1. Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 B.C.--2022) and another new proof linked only, not reproduced
    Romeo Mevstrović · arXiv:1202.3670 · 2012
    arxiv.org/abs/1202.3670
  2. An infinitude of proofs of the infinitude of primes linked only, not reproduced
    L. J. P. Kilford · arXiv:math/0610066 · 2006
    arxiv.org/abs/math/0610066