As you hunt for primes, they get harder to find. Among 1 to 10, four are prime (2, 3, 5, 7) — a 40\% hit rate. Among 1{,}000{,}000 to 1{,}000{,}010, only one is prime (1{,}000{,}003). Among the first hundred integers past 10^{18}, you might find two or three primes if you are lucky. The density visibly thins. A natural question follows:
Do the primes eventually run out? Is there a largest prime?
The answer is no. There are infinitely many primes, and the proof is one of the most famous in all of mathematics. Euclid wrote it down around 300 BCE in Book IX of the Elements. It is short, vivid, and complete — once you read it, there is no more doubt.
The proof (by contradiction)
Suppose, for the sake of argument, that there are only finitely many primes. Call them:
— a finite list, containing every prime that exists. We want to derive a contradiction.
Step 1: build a strange number N.
Multiply all the primes together, then add 1:
For example, if we pretended the only primes were 2, 3, 5, then N = 2 \cdot 3 \cdot 5 + 1 = 31.
Step 2: ask what divides N.
N is an integer greater than 1 (every prime is \geq 2, so N \geq 2 + 1 = 3). Every integer \geq 2 has a prime factor — that is the existence part of the Fundamental Theorem of Arithmetic. So N has some prime factor q.
Step 3: show q is not in the list.
Is q = p_1? If so, then p_1 \mid N. But also p_1 \mid (p_1 \cdot p_2 \cdots p_r) (obviously). So p_1 would divide the difference: p_1 \mid (N - p_1 \cdot p_2 \cdots p_r) = p_1 \mid 1. But no prime divides 1. Contradiction — so q \neq p_1.
The same argument works for each p_i: if q = p_i, then p_i would divide 1, which is impossible. So q is not any of p_1, p_2, \dots, p_r.
Step 4: extract the contradiction.
We assumed that p_1, p_2, \dots, p_r were all the primes. But q is a prime that is not any of them. That contradicts the assumption.
Step 5: conclude.
The assumption that there are only finitely many primes is false. Therefore there are infinitely many primes.
What the proof really says
The trick is this: you give me any finite list of primes — long or short, hand-picked or random — and I can produce a brand new prime that you missed. I do it by multiplying your list, adding 1, and then looking for a prime factor of the result. That prime factor is guaranteed to be outside your list.
No finite list can be complete. Whenever you think you are done, Euclid's construction produces another prime. So the primes have no end.
A worked instance
Take the tiny list \{2, 3, 5\}. Euclid's N = 2 \cdot 3 \cdot 5 + 1 = 31. Now 31 is itself prime, and 31 \notin \{2, 3, 5\} — so our list was incomplete.
Add 31 to the list: \{2, 3, 5, 31\}. Now N = 2 \cdot 3 \cdot 5 \cdot 31 + 1 = 931. Factoring: 931 = 7^2 \times 19. Both 7 and 19 are primes, and neither is in \{2, 3, 5, 31\}. Our list was still incomplete.
Add them: \{2, 3, 5, 7, 19, 31\}. Now N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 19 \cdot 31 + 1 = 123{,}761. Factor: 123{,}761 = 7 \times 11 \times 1607. The prime 11 is new. And 1607 is also prime, and also new.
The construction keeps producing new primes, round after round. You cannot finish the list.
Common confusions
"Is N itself always prime?"
No, and this is the most common misreading of Euclid's proof. People sometimes say the proof constructs a prime by the formula N = p_1 \cdots p_r + 1. That is wrong. The formula produces a number N; N might or might not be prime itself. What the proof guarantees is that N has a prime factor — and that factor is outside the list.
From our worked example: N = 2 \cdot 3 \cdot 5 \cdot 31 + 1 = 931 = 7^2 \times 19. Here N is not prime. But N's prime factors (7 and 19) are new.
"Does the proof require that N be prime?"
No. It only uses the fact that N has some prime factor (which every integer \geq 2 does, by the existence of factorisation). Whether N itself is prime is irrelevant.
"What about N - 1 or N + 2 — why specifically + 1?"
The +1 is doing something specific: it makes N coprime to every prime on the list. If you divide N by any p_i, you get a remainder of 1 — because N is 1 more than a multiple of p_i. So no p_i divides N; therefore N's prime factor must be outside the list.
If you used N = p_1 \cdots p_r (without the +1), then every p_i divides N, and you learn nothing new.
"Can we skip the proof and just check?"
Checking is not proof. The argument "I have listed the first 1000 primes and there always seems to be another one" is evidence but not proof. The danger of relying on evidence is that many number-theory patterns eventually break — the famous Mertens conjecture looked rock-solid for 10^{14} numbers and was later proved false. Euclid's argument is a proof: it settles the matter for all time, without any computation at all.
Why primes thin out but never stop
Here is a subtle tension. The Prime Number Theorem says the density of primes near N is roughly 1 / \ln N — so primes get rarer as N grows. Does "getting rarer" somehow mean "running out eventually"?
It does not. Consider 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots — these numbers get arbitrarily small, but there is still an infinite supply of them. Rarefaction and infinity are compatible. The primes can simultaneously (a) become a smaller fraction of integers as N grows and (b) continue forever.
The harmonic series makes this concrete. The sum \sum_p \frac{1}{p} over all primes — \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \dots — actually diverges (proved by Euler). So not only are there infinitely many primes, there are enough of them to make this sum grow without bound. Far from running out, the primes are abundant in a precise sense.
The historical weight of this theorem
Euclid's proof appears in the Elements, the most influential mathematics book ever written. The proof has remained essentially unchanged for 2300 years — not because mathematicians could not improve it, but because it is already perfect. Short, correct, self-contained, deeply surprising. Whole branches of mathematics grew out of this single argument:
- The style (proof by contradiction) became a fundamental technique.
- The idea of constructing a counterexample from an assumed-complete list is reused constantly in higher math.
- The question "do primes of type X have an infinite count?" generalises in many directions (primes in arithmetic progressions, Gaussian primes, etc.), each needing its own proof.
Indian mathematicians like Bhaskara II and Brahmagupta knew of prime-like results and used them extensively, but the elegant Euclidean argument was the first to settle the infinite-primes question at a stroke.
A compact version of Euclid's proof
Step 1. Suppose the primes are exactly p_1, \dots, p_r (for contradiction).
Step 2. Let N = p_1 p_2 \cdots p_r + 1.
Why this N: it is coprime to every p_i because division by p_i leaves remainder 1.
Step 3. N \geq 2, so N has a prime factor q (existence of factorisation).
Step 4. If q = p_i for some i, then p_i \mid N and p_i \mid p_1 \cdots p_r, so p_i \mid (N - p_1 \cdots p_r) = p_i \mid 1. But no prime divides 1. Contradiction.
Step 5. So q is a prime not equal to any p_i — a new prime, outside the list.
Step 6. The list was supposed to contain all primes. Contradiction.
Conclusion: The assumption fails. There are infinitely many primes.
The whole proof fits in six lines. That is why it is one of the most admired proofs in mathematics.
The one-line takeaway
Assume the primes are a finite list; build N by multiplying them all and adding 1; notice that N has a prime factor that is not on your list — contradicting the "finite" assumption. So the primes cannot be finite, and the list goes on forever. Euclid proved it in 300 BCE in six lines, and the proof has never been improved.
Related: Number Theory Basics · Euclid's Infinite-Primes Tree · Sieve of Eratosthenes · Ulam Spiral · Why is 1 Not Considered a Prime Number?