I was recently wondering why Euclid, the geometer, published a proof that there is an infinite number of primes. I should have known that his proof is geometric. It is:
“Let A, B, and C be distinct lengths that cannot be further divided into lengths of whole numbers (other than the unit segment). Let \(\overline{DE}\) be a length which can be divided by A, B, and C. Now add a collinear unit segment, \(\overline{EF}\), to make segment \(\overline{DF}\). If the measure of \(\overline{DF}\) is prime, then there exists a prime number that is not A, B, or C. If the measure of \(\overline{DF}\) is not prime, then there exists a prime number G that divides \(\overline{DF}\). If G is A, B, or C, then it divides \(\overline{DE}\). But then it would also have to divide the unit segment \(\overline{EF}\). This is absurd. Therefore there exists a prime number that is not A, B, or C.” (Elements 9: 20; English)
Here’s a modernized and generalized version, still being geometric:
A prime number is the length of a segment which cannot be divided into a whole number of smaller segments longer than the unit segment. Let P be the set of all such prime numbers, and assume that P is finite. Then we can construct a segment, \(\overline{AB}\), the length of which is determined by multiplying all elements of P together. The measure of \(\overline{AB}\) can be divided into a whole number by all elements of P. To \(\overline{AB}\) add a collinear segment \(\overline{BC}\) that is one unit long. Let q be the smallest whole number greater than one that evenly divides \(\overline{AC}\). If q is in P, then it divides \(\overline{AB}\). But that means it also divides \(\overline{BC}\). However, the unit segment can’t be divided by anything except 1. So q cannot divide both \(\overline{AC}\) and \(\overline{AB}\). If it cannot divide \(\overline{AB}\), it is not in P. Therefore, there exists a prime number outside of P, which is a contradiction of our original assumption. Hence P is not finite. QED
Naturally, this is a geometric phrasing of the algebraic proof that is typically presented as “Euclid’s proof”:
Let \(P\) be the set of all prime numbers, and let \(P\) be finite. Let \(q = 1 + \Pi P\), and let \(p > 1\) be the lowest factor of \(q\). \(p \in P \Rightarrow (q-1) / p \equiv 0\), and we know \(q / p \equiv 0\), Therefore \(1 / p \equiv 0\). But \( \forall n > 1, 1 / n \equiv 1 \Rightarrow 1 = 0\), which is impossible. Therefore \(P\) is not finite. QED
The proof of infinite primes is a consequence of a broader theorem: Consecutive integers p and p + 1 have no common factors (p > 1). Matt McIrvin points out that Euclid’s proof does not require that \(DE\) be the lowest common multiple, just that it be a common multiple. For instance, take \(P = \{2, 3, 5\}\). Then \(DE = 120\) satisfies the proof, since \(DF = 121\) and so \(G = 11\). For that matter, we could even include factors of \(DE\) not in \(P\), like \(DE = 210\). \(DF = 211\) is prime. For all multiples of 30, none of the factors of one more than that multiple will be in \(P\).
As a geometry teacher, it excites me to see basic mathematical concepts that can be presented geometrically. Year after year, my students have struggled with the concept of prime numbers, and why it’s important to geometry in the first place. So this is a great find for me.
To my reading, this proof only has the thinnest veneer of geometry. What do we gain by moving from integers to lengths of segments here?
Theoretically, nothing. Pedagogically, a lot. My seven year old now understands prime numbers, as “numbers you can only make into one kind of square or rectangle” (1×1 is a special case).
That’s not the point, though. The point is, Euclid visualized mathematics in geometric terms, and this is another case of that. I think it’s interesting to see how different people see the same concept.