Are there infinitely many prime numbers?

Yes. Euclid proved this around 300 BCE. No matter how many primes you collect into a list, the argument constructs a number whose prime factors all lie outside that list, so at least one new prime must exist.

Does Euclid's proof show that N = (p1 x p2 x ... x pk) + 1 is always prime?

No, and this is the most common misstatement of the proof. N only needs to have a prime factor not on the list, which might be N itself or might be a smaller number. For example, 2x3x5x7x11x13 + 1 = 30031, which is NOT prime: 30031 = 59 x 509. Both 59 and 509 are primes absent from the list {2,3,5,7,11,13}, so the proof still works perfectly.

What kind of proof is Euclid's argument?

It is a proof by contradiction (reductio ad absurdum). You assume the opposite of what you want to prove, namely that there are only finitely many primes, and then show that assumption leads to a contradiction.

How does the proof guarantee a prime outside the list?

The constructed number N leaves remainder 1 when divided by any prime on the list, so none of the listed primes divide N. But every integer greater than 1 has at least one prime factor. Therefore N has a prime factor, and that factor cannot be on the list. A prime outside the list is guaranteed.

Is this related to Cantor's diagonal argument or Goodstein's theorem?

All three sit in the same family of results where a simple construction defeats any attempt at a complete finite (or countable) description. Euclid defeats any finite list of primes, Cantor defeats any countable list of real numbers, and Goodstein produces a sequence that defeats the proof power of Peano arithmetic.

Euclid's Proof That There Are Infinitely Many Primes

Somewhere around 300 BCE, Euclid wrote down an argument short enough to fit in a single paragraph. It has never been improved on, because it cannot be. The claim is that the prime numbers go on forever, and the proof is a construction: give me any finite list of primes, and I will hand you a prime that is not on it.

Two thousand years later, the argument still has the quality of a good magic trick. You see every step clearly. You know exactly how it ends. And it still lands.

What a Prime Is, and Why the Question Matters

A prime number is a whole number greater than 1 whose only divisors are 1 and itself. The first few are 2, 3, 5, 7, 11, 13. They sit inside the whole numbers like atoms: every other whole number is built by multiplying primes together. The number 30, for instance, breaks down as 2 times 3 times 5, and there is essentially only one way to do that factoring.

Given that primes are the building blocks of all whole numbers, it is natural to ask: do they run out? Is there a largest prime, beyond which the well is dry? Euclid's answer is no, and the route he takes is elegant enough to follow in a single sitting.

The Setup: Assume the List Is Complete

The argument is a proof by contradiction. You begin by granting the opposition everything they want.

Assume there are only finitely many primes

Suppose, for the sake of argument, that the complete collection of all primes is a finite list: p1, p2, p3, all the way up to pk. No primes exist outside this list. This is the assumption we will destroy.

Now, having collected every prime in existence into that list, build a new number from them.

Constructing the Number That Breaks the List

Form N by multiplying all listed primes together and adding 1

Let N = (p1 times p2 times p3 times ... times pk) + 1. That is: take the product of every prime on the supposedly complete list, then add 1.

This is the key move, and it is worth slowing down to see what it does. Multiplying all the listed primes gives you a number that every prime on the list divides evenly. Adding 1 disrupts all of them at once.

When you divide N by p1, you get a remainder of 1, because the product (p1 times p2 times ... times pk) is divisible by p1, and adding 1 shifts the remainder to 1. The same logic applies to p2, to p3, to every prime on the list. None of them divide N evenly.

The Contradiction

N has a prime factor, but that factor cannot be on the list

Every integer greater than 1 has at least one prime factor. This is a consequence of the Fundamental Theorem of Arithmetic: keep factoring until you cannot anymore, and you are left with primes. So N has a prime factor. Call it q.

We just showed that no prime on the list divides N. Therefore q is not on the list. But we assumed the list contained every prime. That is the contradiction: we have found a prime, q, that is not on the supposedly complete list.

The assumption must be false

Since the assumption that there are only finitely many primes leads directly to a contradiction, the assumption is false. There is no finite list that contains all the primes. The primes go on forever.

The Counterexample That Makes the Proof Honest

Here is where many popular accounts of Euclid's proof go astray. They claim that N itself is always prime. It is not, and the distinction matters.

Take the list 13. The product is 2 times 3 times 5 times 7 times 11 times 13, which equals 30030. Add 1 and you get N = 30031.

Is 30031 prime? No.

30031 = 59 times 509.

Both 59 and 509 are prime, and neither appears on the list 13. This is exactly what the proof predicts: not that N is prime, but that N's prime factors are absent from the list. In this case the prime factors are 59 and 509, two primes that were left off the finite list. The argument is vindicated, but the vindication comes from the factors, not from N itself.

What the Proof Actually Says

It is worth pausing on the shape of the argument, because it is unusually clean.

You do not construct the missing prime explicitly. You do not search for it. You prove it must exist by showing that assuming otherwise leads to a logical dead end. The prime q hiding in the factors of N might be easy to find (as 59 and 509 are, if you try a few small divisors of 30031) or it might be enormous. The proof does not care. Its power comes from inevitability: whatever list you hand over, the construction finds a gap.

This connects naturally to other proofs that proceed by the same spirit of "assume the opposite, watch it collapse." Cantor's diagonal argument uses the same structure at a larger scale: assume a complete list of real numbers exists, and then construct a real number provably absent from it. The echo of Euclid is unmistakable.

Why the Primes Never Thin Out Completely

One thing the proof does not tell you is how far apart primes can be, or how large the next prime after any given one might be. Euclid's argument only guarantees existence: somewhere beyond any finite collection, another prime lives. The distribution of primes across the number line is a much harder question, and remains one of the deepest open areas of mathematics today.

What the proof does tell you is structural. The prime numbers cannot be exhausted by any finite means. You could dedicate a lifetime to listing primes, and you would always be listing into an infinite remainder. Every prime you found was real, but the ones ahead of you were just as real, just as numerous, and just as unreachable by a finite list.

For a sense of how quickly numbers can grow when you build with multiplication and exponents, the article on understanding exponents intuitively is a natural companion: the product p1 times p2 times ... times pk grows faster than you might expect, and that growth is part of why N ends up so large so quickly.

The Zen of It

Euclid's proof is more than two millennia old, and mathematicians have found hundreds of proofs of the same result since. None of them has made this one obsolete. It keeps its place not because it is the cleverest or the most general, but because it is the most transparent.

You see the whole argument in one pass. The construction is natural. The contradiction is sharp. There is no step where you have to take something on faith or trust that a complicated machine is doing what it claims.

What the proof asks you to hold in mind is a single idea: any finite list of primes is already incomplete. Not because the list is badly chosen, but because the primes are the kind of thing that cannot be contained by any finite count. They belong to the infinite in the same way the integers do, or the fractions do, or the points on a line do. The proof does not tell you where the next prime is. It tells you the next prime is always there.

That is enough. That has always been enough.

For other results that share this spirit of inevitability, Goodstein's theorem shows a sequence that always returns to zero despite growing past anything writable, using the same logic of "something must happen because the alternative is impossible." The family of arguments is worth knowing. Each one is a different angle on the same underlying fact: mathematics contains no escape hatches. The structure holds.