Why There Are Infinitely Many Primes

Primes get rarer as numbers grow. Among the first 100 whole numbers, 25 are prime. Among numbers near a billion, only about 1 in 21 is. It's natural to wonder whether they eventually run out, leaving a last, largest prime.

They don't. Around 300 BC, Euclid proved it with an argument so short it fits on an index card. More than two thousand years later, it's still considered one of the most beautiful proofs in mathematics.

The Proof Doesn't Build a Prime

Many people remember Euclid's proof as "multiply all the primes together and add 1, and you get a new prime." That's not what the proof says, and the claim is actually false.

Try it with the first six primes:

2 × 3 × 5 × 7 × 11 × 13 + 1 = 30,031

But 30,031 isn't prime. It equals 59 × 509. Check it yourself with the prime factorization of 30,031.

What the proof really shows is subtler: the result has a prime factor that wasn't on your list. Here 59 and 509 are both new primes. Either way, the list was incomplete.

Euclid's Proof, Step by Step

The argument appears as Proposition 20 in Book IX of Euclid's Elements. In modern language:

1. Suppose there are only finitely many primes: p₁, p₂, …, pₙ.
2. Multiply them all together and add 1:

   N = p₁ × p₂ × … × pₙ + 1
   

3. N is bigger than 1, so it has at least one prime factor. Call it q.
4. Could q be one of p₁, …, pₙ? Dividing N by any of them leaves a remainder of 1. So none of them divides N.
5. Therefore q is a prime not on the list.
6. That contradicts the assumption that the list contained every prime.

So no finite list can contain all the primes. There are infinitely many.

This is a proof by contradiction: assume the opposite of what you want to prove, and show that assumption leads to something impossible. (Strictly speaking, Euclid phrased it more directly: given any finite set of primes, there's always another prime. Either way, the logic is the same.)

Why Step 4 Works

Step 4 is the heart of the proof, and it uses modular arithmetic. If p divides a product P, then:

P ≡ 0 (mod p)
P + 1 ≡ 1 (mod p)

A number that leaves remainder 1 when divided by p can't be a multiple of p. That's all there is to it. The number theory formulas page covers the rules of congruences.

Step 3 Relies on a Deeper Fact

Why must N have a prime factor? Because of the fundamental theorem of arithmetic: every whole number greater than 1 is either prime or a product of primes, in exactly one way (apart from the order).

If N is prime itself, it's the new prime. If not, break it into factors, and keep breaking until only primes remain. The process has to stop, because the factors keep getting smaller. You can watch this happen for any number with the prime factorization tool.

How Many Primes Are There?

Knowing primes are infinite leaves a natural follow-up: how common are they? The prime number theorem, proved independently by Jacques Hadamard and Charles de la Vallée Poussin in 1896, says the number of primes up to x, written π(x), is approximately:

π(x) ≈ x / ln(x)

Near a number x, roughly 1 in every ln(x) numbers is prime. The ratio between the actual count and the estimate approaches 1 as x grows. Browse the list of prime numbers to feel how they thin out.

An Insider Reference: A Different Proof From Euler

In 1737, Leonhard Euler gave a completely different proof. He showed that the sum of the reciprocals of the primes diverges:

1/2 + 1/3 + 1/5 + 1/7 + 1/11 + … = ∞

If there were only finitely many primes, that sum would be a finite number. Euler's proof reveals more than Euclid's: primes aren't just infinite, they're dense enough that their reciprocals add up to infinity. (By contrast, the reciprocals of the perfect squares, 1 + 1/4 + 1/9 + …, add up to just π²/6.) The sum of prime reciprocals does grow extraordinarily slowly, roughly like ln(ln(x)).

In 1955, a young Hillel Furstenberg published yet another proof, using topology. Mathematicians keep finding new proofs because each one shows a different face of the primes.

The Largest Known Prime

Since there's no largest prime, there's always a race to find a bigger one. In October 2024, the Great Internet Mersenne Prime Search announced a new record:

2¹³⁶²⁷⁹⁸⁴¹ − 1

It has 41,024,320 digits. It was found by Luke Durant, a former NVIDIA engineer, using thousands of cloud GPUs. Euclid's proof guarantees that an even larger prime exists; finding it is another matter.

Two Concepts Worth Knowing

Proof by Contradiction

In a proof by contradiction, you assume a statement is false and show that assumption leads to an impossibility. It's one of the most powerful tools in mathematics. The proof that √2 is irrational uses it too.

Prime Factorization

Prime factorization writes a number as a product of primes: 360 = 2³ × 3² × 5. The fact that this is unique is what makes primes the "atoms" of arithmetic.

Quick Answer: Why Are There Infinitely Many Primes?

Assume there are finitely many primes, multiply them all and add 1. The result leaves remainder 1 when divided by each listed prime, so none of them divides it. But it must have some prime factor, which means a prime was missing from the list. So the primes can never run out.

Try Them Yourself

• Prime Factorization of 30,031: see Euclid's "product + 1" in action
• Is 2,311 Prime?: check 2 × 3 × 5 × 7 × 11 + 1
• List of Prime Numbers: watch primes thin out
• Prime Numbers: properties and patterns
• Number Theory Formulas: congruences and divisibility
• Pierre de Fermat: another giant of prime number theory

Try Euclid's construction with the first 1, 2, 3, 4, 5 and 6 primes. Some results are prime, some aren't, and every single one contains a prime you didn't start with.