Primes are the atoms of the number system — every whole number bigger than 1 is built by multiplying primes together, and in only one way (that's the Fundamental Theorem of Arithmetic). So a natural question follows immediately: do we ever run out of atoms?

As you climb the number line, primes get rarer. Between 1 and 100 there are 25 of them; between 10{,}000{,}000 and 10{,}000{,}100 there are typically only one or two. Vast empty deserts open up with no primes at all — the gap between consecutive primes can be made bigger than any number you name. It would be entirely reasonable to guess that, somewhere far up the number line, the very last prime is sitting alone, with nothing but composites beyond it. Every whole number system we build — clocks, codes, cryptography — leans on primes never actually giving out. Euclid settled the question over two thousand years ago, with an argument so short and so clean that it is still, essentially unchanged, one of the very first pieces of "real" mathematics most people ever meet.

Euclid's proof

The argument is a proof by contradiction: assume the opposite of what we want, and show that assumption collapses. Suppose, for the sake of argument, that there were only finitely many primes in existence — every last one of them. Then we could write them all down in a complete, finite list:

Now build one carefully chosen number by multiplying every prime on that list and adding one:

By the Fundamental Theorem of Arithmetic, N has some prime factor p (every integer bigger than 1 does). But look at what happens when you divide N by any prime on our list: dividing p_1 p_2 \cdots p_k by p_i leaves no remainder, so dividing N = p_1 p_2 \cdots p_k + 1 by p_i always leaves remainder 1 — never 0. So p, the prime factor we just found, cannot be any of p_1, \dots, p_k.

We have just produced a prime that is missing from a list that was supposed to be every prime. That's the contradiction. The only thing that could have gone wrong is our starting assumption — so there cannot be a finite list of all the primes. The primes never run out.

This isn't just an abstract curiosity, either. The whole idea of using primes to lock up information — the encryption that protects a bank card number flying across the internet — depends on there always being fresh, unpredictable primes available, no matter how large a number you need. If the primes ever ran dry, that whole toolbox would eventually break. Euclid's proof is the ultimate guarantee behind it: the supply never, ever ends.

A worked example: catching the argument in the act

The proof works for any finite list, no matter how it was chosen — that's exactly its power. To see it up close, pretend someone hands you a short "complete" list of primes:

Multiply them together and add one:

Check the remainders directly: 31 = 2 \times 15 + 1, so dividing by 2 leaves remainder 1; likewise 31 = 3 \times 10 + 1 and 31 = 5 \times 6 + 1. Not one of 2, 3, 5 divides 31 exactly. And indeed, 31 itself turns out to be prime — a brand new prime, sitting completely outside the list \{2,3,5\}. Whoever claimed that list was "all the primes" was wrong the moment we exhibited 31. Feed the proof any finite list whatsoever — a thousand primes, a million — and the same trick manufactures a witness that the list was incomplete. That is the whole engine of the theorem, running on three small numbers.

A second try, with a slightly longer starting list, shows the same trick doesn't get any weaker as the list grows. Take \{2, 3, 5, 7\}:

Check divisibility by each prime on the list in turn — 211 is odd, not a multiple of 3 (its digits sum to 4), doesn't end in 0 or 5, and 211 = 7\times 30 + 1. None of 2, 3, 5, 7 divides it, and in fact 211 is itself prime — a fifth prime the list \{2,3,5,7\} never mentioned. Compare that with the very next example below, where Euclid's number comes out composite instead: either way, a brand new prime gets exposed.

A contradiction, not a formula

There's a second trap right next to the first one: Euclid's argument is not a recipe for generating primes. A proof by contradiction only needs to show that assuming "finitely many primes" leads somewhere impossible — it doesn't need to hand you an efficient way to actually find the new prime. Notice what the proof does and doesn't give you:

• It gives you a guarantee: whatever finite list of primes you start from, a prime outside that list exists somewhere.
• It does not tell you which number that missing prime is without more work — finding it means factoring N, which gets brutally hard as N grows (as 30031 already hints).
• It does not produce primes in order, and repeating the trick on bigger and bigger lists is a hopelessly slow way to search for primes compared with a proper sieve.

So Euclid's theorem answers a pure existence question — "do the primes ever stop?" — with a resounding no, while staying completely silent on the much harder practical question of how to list them. Existence proofs like this one are common throughout mathematics: they settle whether something is out there without necessarily saying how to go and get it.

Inexhaustible, but thinning

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

It's worth seeing just how empty those "prime deserts" can get, precisely because it makes Euclid's guarantee feel more surprising, not less. Pick any number of empty steps you like, say n = 6, and look at these five numbers in a row:

where 6! = 720. Every single one is composite: 720+2=722 is divisible by 2 (because 720 and 2 both are), 720+3=723 is divisible by 3 (because 720 and 3 both are), and so on up to 720+6=726, divisible by 6. That's a run of five consecutive numbers with no prime among them — and the same trick with a bigger factorial n! builds a prime-free run as long as you like, anywhere you like. Deserts of any length are guaranteed to exist. And yet Euclid's theorem guarantees, with equal certainty, that no matter how far out you travel, the desert always ends and another prime is waiting on the other side. Both facts are true at once — arbitrarily long gaps, and an endless supply — and that tension is exactly what makes the deeper study of prime distribution so rich.