Do the primes ever run out? As you climb the number line they grow rarer — vast deserts appear with no primes at all. It would be reasonable to guess that somewhere up high the last prime sits alone. Euclid proved otherwise, more than two thousand years ago, with an argument so clean it is still the first piece of "real" mathematics many people ever see.

Euclid's proof

The argument is a proof by contradiction. Suppose, for the sake of argument, that there were only finitely many primes — list them all:

Now build one carefully chosen number by multiplying them all and adding one:

By the Fundamental Theorem of Arithmetic, N has some prime factor p. But N leaves remainder 1 when divided by any prime on our list — so p is not among p_1, \dots, p_k. We have produced a prime missing from a list that was supposed to be complete. The contradiction means no finite list can hold them all.

A common misreading

It is tempting to say "N is itself a new prime." Not quite — N need not be prime. For example 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13 + 1 = 30031 = 59 \times 509. The proof only needs that N has a prime factor outside the list — and it always does. The new prime is hiding inside N, not equal to it.

The primes are inexhaustible — but thinning

Infinitely many, yes — but they do thin out, and Euclid's proof says nothing about how fast. That quantitative question — roughly how many primes lie below a given size — is subtler and far deeper, and it drives the rest of this stage and, ultimately, the Prime Number Theorem.