Euclid's proof that there are infinitely many primes

Frequently asked questions

Does Euclid's proof tell us how far apart consecutive primes can be?

It gives only a very loose upper bound (since $q \le N = p_1 p_2 \cdots p_n + 1$ , the $(n+1)$ -st prime is at most $1$ more than the product of the first $n$ primes). Much tighter results about the distribution and spacing of primes require analytic number theory, such as the Prime Number Theorem and bounded gaps between primes.

Source

Euclid of Alexandria, -300

Euclid's Elements, Book IX, Proposition 20 (ed. David E. Joyce, after Thomas L. Heath)

Step 6 of 7: Contradiction and conclusion: infinitely many primes exist

Previous step Next step

In plain words

We now hold two facts side by side: the prime q divides N with remainder 0, whereas every single prime on the list L leaves remainder 1 when dividing N. Therefore q cannot be any of the primes on the list — we have caught a prime that the supposedly complete list left out.

q \mid N \text{ and } (\forall\, p_i \in L,\ p_i \nmid N) \implies q \notin \{p_1, p_2, \dots, p_n\}

Detailed analysis

Combine Step 4 and Step 5: Step 5 gave us a prime number $q$ that divides $N$ ( $q \mid N$ ), while Step 4 showed that no prime $p_i$ in the list $L = \{p_1, p_2, \dots, p_n\}$ divides $N$ ( $p_i \nmid N$ ). Consequently, $q$ cannot equal $p_i$ for any $i \in \{1, \dots, n\}$ , which means $q \notin L$ is a brand-new prime number not in our list.

If we assumed at the start that $L$ was the complete list of all primes in existence, finding a prime $q \notin L$ directly contradicts that assumption. Since $n$ was an arbitrary finite number, no finite list can ever contain all prime numbers. As Euclid concludes at the end of Book IX, Proposition 20: "Therefore, prime numbers are more than any assigned multitude of prime numbers."

Knowledge used in this step

Prime numbers