## 2024-07-08

### Yes, Euclid's Proof of Infinite Primes Uses Contradiction

It's common nowadays in conversations about the method of proof-by-contradiction for someone to pop in and say, "People think Euclid's proof of there being infinite prime numbers uses proof-by-contradiction, but it doesn't, it's a direct proof". For example, the current Wikipedia article on Euclid's theorem says this:

Euclid is often erroneously reported to have proved this result by contradiction beginning with the assumption that the finite set initially considered contains all prime numbers, though it is actually a proof by cases, a direct proof method. The philosopher Torkel Franzén, in a book on logic, states, "Euclid's proof that there are infinitely many primes is not an indirect proof..."

Okay, admittedly Euclid's theorem is not in its entirety structured as a proof by contradiction. Yes, there's a proof by cases, in which a number of the form $$lcm(ABC) + 1$$ is assessed as being either prime or not prime. But the core of that second case is clearly a proof by contradiction!

If we look at Euclid's original text for the second case, we see the following. Given that $$lcm(ABC) + 1$$ is not prime, Euclid takes $$G$$ to be some prime number that divides it. He then reasons like this (looking at the Fitzpatrick translation of Heiberg's presentation of the Greek):

I say that $$G$$ is not the same as any of $$A, B, C$$. For, if possible, let it be... [some logic here]... The very thing is absurd. Thus, $$G$$ is not the same as one of $$A, B, C$$.

This form is patently a proof by contradiction, and use of the phrase with "absurd" (in the original Greek, "ὄπερ ἄτοπον") highlights that fact.

While the overall superstructure of Euclid's theorem is not a proof by contradiction... Yes Virginia, Euclid's theorem uses a proof by contradiction, and it's an essential part of his proof that there are infinite primes.