Euclid’s Proof That Primes Never Run Out

Do the primes run out?

A prime number has exactly two factors: 1 and itself. The primes begin 2, 3, 5, 7, 11, 13, 17, 19, and they thin out as the numbers grow. There are 25 primes between 1 and 100, but only 14 between 901 and 1000.

So it is a fair question whether they stop altogether: is there a largest prime? The Greek mathematician Euclid answered it around 300 BC. There is no largest prime, and the primes never run out.

the primes up to 50

The 15 primes up to 50 are ringed. Checking more numbers can find more primes, but it can never show that they go on forever.

Suppose the list is complete

Euclid's proof is a proof by contradiction. It supposes the opposite of what it wants to prove, and shows that the supposition leads to something impossible.

So suppose the primes did run out, and every prime there is could be written on one finite list. To see the argument with real numbers, try a short list first: suppose 2, 3, 5 and 7 were the only primes.

Multiply every prime on the list together and add 1: 2 × 3 × 5 × 7 = 210, and 210 + 1 = 211. Call this new number N.

Nothing on the list divides it

210 is a multiple of every prime on the list, because each of them is one of its factors. So N = 211 is exactly 1 more than a multiple of each: 211 = 2 × 105 + 1, 211 = 3 × 70 + 1, 211 = 5 × 42 + 1 and 211 = 7 × 30 + 1.

Dividing 211 by any prime on the list leaves remainder 1, not 0. The multiples of 7 near 211 are 210 and 217, and 211 falls between them. So none of the primes on the list is a factor of N.

$2 \times 3 \times 5 \times 7 + 1 = 211 \equiv 1 (mod 2, 3, 5, 7), prime$

211 = (2 × 3 × 5 × 7) + 1 leaves remainder 1 when divided by each of them, so none is a factor, and 211 is itself a prime that was not on the list

Take the first six primes and read what their product + 1 is

With the four primes up to 7, the new number is 211, and each prime on the list leaves remainder 1. Slide k to 6 to use the six primes up to 13: the new number is 30,031, and every prime on the list leaves remainder 1 again.

So some prime is missing

Every whole number above 1 has at least one prime factor. If the number is prime, it is its own prime factor. If it is not prime, its prime factorization is made of primes, and each of them is a factor.

So N has a prime factor. That prime is not on the list, because no prime on the list divides N. The list was supposed to hold every prime, and here is a prime it does not hold. The supposition has led to a contradiction, so it was false: no finite list holds every prime.

The new number need not be prime

Take the six primes up to 13. Their product is 30,030, so the new number is 30,031. It leaves remainder 1 when it is divided by 2, 3, 5, 7, 11 or 13. But 30,031 is not prime: 30,031 = 59 × 509.

The proof still works, because it never claimed that the new number is prime. It claimed that the new number has a prime factor missing from the list, and it does: 59 and 509 are both primes, and neither is on the list.

Any finite list

Nothing in the argument depended on which primes were on the list. Take any finite list of primes, multiply them all together and add 1. Every prime on the list leaves remainder 1, so the new number has a prime factor that is not on the list.

The missing prime can even be smaller than the listed ones. From the list 3 and 5, the new number is 3 × 5 + 1 = 16 = 2 × 2 × 2 × 2, and its only prime factor is 2, which the list left out.

So however many primes are written down, there is always one more. There are infinitely many primes.

Testing whether 211 is prime

To decide whether 211 is prime, there is no need to try every number up to 211. If 211 were not prime, it would be a product of two factors, each bigger than 1. Both factors cannot be 15 or more, because then the product would be at least 15 × 15 = 225, which is more than 211.

So one of the two factors would be 14 or less. That factor has a prime factor of 13 or less, and that prime would divide 211 as well. So only the primes 2, 3, 5, 7, 11 and 13 need testing. The first four leave remainder 1, 211 = 11 × 19 + 2, and 211 = 13 × 16 + 3. None of them divides 211, so 211 is prime. With the list 2, 3, 5 and 7, the prime missing from the list is 211 itself.

Worked example: One More Than a Product of Primes: Mei's List and Her Claim

Question Mei is building a list of primes for a coding club. She starts with 2, 3, 5 and 7 and forms the number N = 2 × 3 × 5 × 7 + 1. (a) Show that N is not divisible by any prime in her list, and decide whether N is prime. (b) Mei concludes that one more than a product of primes is always prime. Test her claim on 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031, given that 30031 = 59 × 509, and say what Euclid's argument does guarantee.

1.N = 2 × 3 × 5 × 7 + 1 = 210 + 1 = 211. The number 210 is a multiple of each of 2, 3, 5 and 7, so 211 leaves a remainder of 1 when it is divided by any of them. No prime in the list divides N.

N = 210 + 1 = 211. Since 210 is a multiple of 2, 3, 5 and 7, each of them leaves a remainder of 1.
2.To decide whether 211 is prime, test the primes whose squares are not more than 211. Since 15² = 225 is more than 211, the primes to test are 2, 3, 5, 7, 11 and 13. The first four leave a remainder of 1, and 211 = 11 × 19 + 2 and 211 = 13 × 16 + 3.

15² = 225 is more than 211, so only 11 and 13 are left to test: 211 = 11 × 19 + 2 and 211 = 13 × 16 + 3.
3.(a) No prime up to 13 divides 211, so 211 is prime. It is a prime that is not in Mei's list.

(a) No prime up to 13 divides 211, so 211 is prime, and it is not in the list.
4.For the longer list, 2 × 3 × 5 × 7 × 11 × 13 = 30030, so the new number is 30031. But 59 × 509 = 30031, so 30031 is not prime, and Mei's claim is false.

2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509, which is not prime.
5.(b) Euclid's argument guarantees less than Mei claims, and it is still enough. Each of 2, 3, 5, 7, 11 and 13 leaves a remainder of 1 when it divides 30031, so every prime factor of 30031 is outside the list. The factors 59 and 509 are both prime, and both are new.

(b) The claim is false, but every prime factor of 30031 is outside the list: 59 and 509 are new primes.

Answer: (a) 211 leaves a remainder of 1 when it is divided by each of 2, 3, 5 and 7, and it is prime; (b) the claim is false, because 30031 = 59 × 509, but 59 and 509 are primes that are not in the list

Common mistakes

Saying that 211 is prime only because 2, 3, 5 and 7 do not divide it. A number below 15² can still have the factor 11 or 13, so those two primes must be tested as well.
Concluding from 30031 = 59 × 509 that Euclid's proof fails. The proof never says that the new number is prime. It says that the new number has a prime factor that is not in the list, and 59 is such a factor.

More number theory problems, worked step by step →

The usual mistakes

Saying that the product plus 1 is always prime. 30,031 = 59 × 509 shows that it is not. What the proof guarantees is a prime factor that is not on the list.

Saying that the proof finds the next prime. After 2, 3, 5 and 7 the next prime is 11, not 211. The proof only shows that some prime is missing from the list.

Stopping at "nothing on the list divides N". That alone is not the contradiction. It becomes one with the fact that every whole number above 1 has a prime factor.