On this page
Ask how we know the primes never run out, and someone usually says: multiply all the primes, add one, and you get a new prime. The first half is Euclid's argument. The second half is a mistake, and seeing why is what makes the proof make sense.
What is Euclid's proof that there are infinitely many primes?
The proof is Proposition 20 of Book IX of Euclid's *Elements*, which says that "prime numbers are more than any assigned multitude of prime numbers" (David Joyce's translation, Clark University). Euclid taught at Alexandria and lived roughly from 325 BC to 265 BC; his *Elements* has 13 books, and Books 7 to 9 are about numbers (MacTutor History of Mathematics).
In modern words, the argument has five steps:
Take any finite list of primes p₁, p₂, …, pₙ.
Multiply them and add one: N = p₁ × p₂ × … × pₙ + 1.
N is bigger than 1, so it has at least one prime factor. Call it q.
q cannot be any prime on the list, because dividing N by any of them leaves remainder 1.
So q is a prime that is not on the list. Whatever list you start with, there is always another prime.
Step 3 rests on the fact that every whole number above 1 is either prime or a product of primes, which is the heart of how to use the fundamental theorem of arithmetic.
Euclid did not actually assume there are only finitely many primes; he took any finite set and showed a prime exists outside it (Euclid number, Wikipedia). Textbooks often rewrite it as a proof by contradiction, which is also correct; our guide to proving root 2 is irrational by contradiction walks through that style slowly.
Is the product of primes plus one always prime?
No. The Prime Pages put it plainly: "It is a common mistake to think that this proof says the product p₁p₂…pᵣ+1 is prime" (The Prime Pages).
If you multiply the first few primes in order, the first composite result is 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031, which equals 59 × 509 (Euclid number, Wikipedia).
The trap is easy to fall into because the pattern holds at first. Taking the first 1, 2, 3, 4 and 5 primes gives 3, 7, 31, 211 and 2311 (OEIS A006862), and all five are prime; the next prime of this kind only comes when you use the first 11 primes (OEIS A014545). Whether infinitely many numbers of this form are prime is still not known (Euclid number, Wikipedia).
Why does the proof still work if the number is not prime?
Because the proof never needs N to be prime. Euclid's own text splits into two cases (Book IX, Proposition 20): if the new number is prime, it is a new prime; if it is not, some prime divides it, and that prime cannot be on the list. Either way you get a prime you did not have.
Try it on small lists you can check by hand:
List {3, 5}: 3 × 5 + 1 = 16 = 2 × 2 × 2 × 2. The new prime is 2.
List {2, 7}: 2 × 7 + 1 = 15 = 3 × 5. The new primes are 3 and 5.
List {2, 3, 5, 7, 11, 13}: the product plus one is 30031 = 59 × 509. Neither 59 nor 509 was on the list.
How do you write this proof in an exam?
A five-line version:
Let p₁, p₂, …, pₙ be any finite list of primes.
Let N = p₁p₂…pₙ + 1. Then N > 1, so N has a prime factor q.
Each pᵢ divides p₁p₂…pₙ, so N leaves remainder 1 when divided by pᵢ. Hence q ≠ pᵢ for every i.
So q is a prime not in the list.
Therefore no finite list contains all primes, and there are infinitely many primes.
Then check your answer:
Did you say why N has a prime factor (N > 1)?
Did you give the reason q is not on the list (remainder 1)?
Did you avoid writing "N is prime"?
Did your last line say what was proved?
Parents can test understanding with one question: "Is 30031 prime? If not, where does the proof get its new prime from?" A child who can answer that has understood the proof, not memorised it.
Where to practise next
If you want to see how thinly primes are spread among small numbers, try the probability that a number from 1 to 100 is prime. If a step such as "every number above 1 has a prime factor" feels shaky, the Fermi Concept Library gives each mathematics concept its own lesson and shows where it sits in the map. To test yourself on proofs like this one, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
