Euclid's proof that there are infinitely many primes

Frequently asked questions

Why did Euclid write his proof with only three primes A, B, C instead of n primes?

Ancient Greek mathematics had no subscript notation like $p_1, p_2, \dots, p_n$ . As David Joyce notes in his commentary on Elements IX.20, Euclid routinely used three representative letters ( $A, B, C$ ) to stand for an arbitrary finite collection, while making sure every step of the reasoning works identically for any finite number $n$ of primes.

Source

Euclid of Alexandria, -300

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

Step 2 of 7: Set up the plan: start with any finite list of primes

Previous step Next step

In plain words

Suppose someone claims they have written down the complete, final list of all prime numbers in the universe on a sheet of paper. To prove them wrong, we do not need to find infinitely many primes at once — we just need a reliable recipe that takes their sheet of paper and produces one single prime number that is missing from it.

L = \{p_1, p_2, \dots, p_n\}

Detailed analysis

We let $L = \{p_1, p_2, \dots, p_n\}$ be any finite list of prime numbers. In modern expositions, this is usually framed as a proof by contradiction: assume for contradiction that there are only finitely many primes in total, so that $L$ is the complete list of every prime that exists.

In Euclid's original wording in Book IX, Proposition 20 ("Let A, B, and C be the assigned prime numbers; I say that there are more prime numbers than A, B, and C"), the argument is stated constructively for any assigned finite list $L$ , and uses a small contradiction only inside a later sub-step. Either way, the plan is identical: starting from the finite list $L = \{p_1, p_2, \dots, p_n\}$ , we will construct a new number $N$ and use it to uncover a prime $q \notin L$ .

Terms in this step

Proof by contradiction: A method of proof that establishes a statement is true by temporarily assuming the opposite is true and showing that this assumption leads to a logical impossibility.

Knowledge used in this step

Prime numbers