Today, we take a break from our recent philosophical musings to return to some good old-fashioned mathematics (indeed, the mathematics today could be seen as all being “old-fashioned,” as the theorem we will be considering dates back to the ancient Greeks).
I’m sure my readers have all been introduced to the prime numbers, but, to refresh any memories, let me remind you that a prime number is a natural number, at least 2, that has no divisors other than 1 and itself. The first few prime numbers are, therefore: 2, 3, 5, 7, 11, 13…
The prime numbers can be thought of as the building blocks of number theory, as the backbone of the natural numbers. They have occupied a central place in mathematics and offered endless fascination for millennia. They are a source of great mystery even today.
In this post, we look at a classic theorem, commonly attributed to Euclid. Euclid’s proof is one of the gems of mathematics, a proof that is taught to every mathematician at the beginning of their true mathematical career. The theorem, as we will state it, is simply this:
Euclid’s Theorem: There are infinitely many prime numbers.
Euclid himself did not state the theorem in exactly this form, perhaps because of the ancient Greeks’ general antipathy towards the existence of infinite sets. He instead put forward the equivalent statement, “For every finite set of prime numbers, there is a prime number not in that set.”
Euclid’s Theorem has collected a vast and varied array of delightful proofs throughout the years, and, in a proposed infinite series of blog posts, I plan to cover all of them. Today, we will look at three proofs, from three very different centuries, all using only elementary number-theoretic techniques. First, of course, is Euclid’s proof itself.
Proof One (Euclid): Suppose that is a finite set of prime numbers. We will show that there is a prime number that is not in . To do this, let , and let . For all , divides with no remainder (as ), so, as and , does not divide . Since and every integer greater than 1 has prime divisors, there is at least one prime, , that divides . But we just saw that no element of divides , so is a prime that is not in .
The next proof we will consider is due to the eighteenth-century German mathematician Christian Goldbach, largely known today for the statement of the still unproven Goldbach’s Conjecture. This proof (like Goldbach’s Conjecture itself) appears in a letter from Goldbach to Leonhard Euler (whose analytic proof of Euclid’s Theorem we will visit in a future post).
Proof Two (Goldbach): For each natural number , let , so , etc. ( is known as the Fermat number.)
Claim 1: For every natural number , .
Proof of Claim 1: Suppose that the Claim is false, and let be the smallest natural number such that . Since the Claim can easily be verified by inspection for , we may assume . But now we have the following sequence of calculations where, because we are assuming that is the smallest counterexample to the Claim, we can use the fact that .
But this calculation shows that is not a counterexample to our Claim, contradicting our assumption and finishing the proof of the Claim.
We now need a very simple number-theoretic Claim.
Claim 2: If and are natural numbers, is a prime, and divides both and , then divides .
Proof of Claim 2: Suppose and , where and are natural numbers. Then , so divides .
Claim 3: If are natural numbers, then there is no prime number such that divides both and .
Proof of Claim 3: Suppose that the Claim is false and that there are natural numbers and a prime number such that divides both and . Note that is one of the factors in the product , so divides . Since , we also conclude that divides , so, by Claim 2, we know that divides . As is prime, this means that . But and are both odd, so this is impossible.
We are now ready to finish the proof. For each natural number , choose a prime number that divides . By Claim 3, for all natural numbers , we have , so is an infinite set of prime numbers.
Remark: The Fermat numbers were introduced, unsurprisingly, by the seventeenth-century French mathematician Pierre de Fermat (of Fermat’s Last Theorem fame). Fermat conjectured that every Fermat number is in fact prime (this would obviously imply Claim 3 from the previous proof). The first four Fermat numbers (3, 5, 17, 257) are easily verified to be prime, and the next Fermat number, 65537, can be seen to be prime with a bit more work. However, Euler proved in 1732 that is not prime. Indeed, . Many mysteries remain regarding the Fermat numbers. For example, even the following two very basic questions remain unsolved to this day:
- Are there infinitely many prime Fermat numbers?
- Are there infinitely many non-prime Fermat numbers?
The Fermat numbers grow so quickly that, even with computers, it can be hard to analyze even “relatively small” Fermat numbers. For example, it is unknown whether or are prime. On the other hand, the truly gigantic number is known to be non-prime: one of its prime factors is .
Finally, a proof that combines ideas from Euclid’s and Goldbach’s proofs was given recently by Filip Saidak.
Proof Three: (Saidak) Note first that, for every natural number , we have that and do not have any shared prime divisors. Now define an infinite sequence of natural numbers, as follows. Let be any natural number that is at least 2. Let . Since and do not share any prime divisors, and since both and have at least one prime divisor, it follows that must have at least 2 distinct prime divisors.
Now let . Again, and do not have any shared prime divisors. We have shown that has at least 2 distinct prime divisors, and we know that has at least one prime divisor, so must have at least 3 distinct prime divisors. Continuing in this way, defining for every natural number , one proves that, for each natural number , the number has at least distinct prime divisors. In particular, there are infinitely many prime numbers.
Stay tuned for a future post, in which we will provide proofs of Euclid’s Theorem from further flung areas of mathematics, including real analysis and topology.