Euclid’s Proof of Infinitely Many Primes
How we know there are infinitely many prime numbers, explained briefly
Last week I wrote about sexy primes, a type of prime number. I mentioned that we’ve known that there are infinitely many prime numbers since about 300 B.C., thanks to a proof documented by Euclid. It’s a nice proof! It’s also a great example of a proof by contradiction. So I’m going to go over Euclid’s proof of infinitely many primes.
What’s a Proof by Contradiction?
Euclid’s proof is a type of proof called “proof by contradiction.” A proof by contradiction works in 3 steps:
- Assume the opposite of whatever you’re trying to prove.
- Show that assuming the opposite leads to some paradox, absurdity, or contradiction.
- Since assuming the opposite leads to a contradiction, the original statement must be true.
If you’ve ever seen a soap opera, you’ve probably seen a proof by contradiction. Two soap opera characters will often have conversations like this:
Debbie: You’re cheating on me with the maid!
Robert: No I’m not.
Debbie: Well if you’re not cheating… [pulls out Robert’s phone] then how did these texts end up on your phone?
[dramatic music]
This exchange not only shows the collapse of Robert and Debbie’s marriage, it also shows the structure of a proof-by-contradiction:
- Debbie wants to prove: “Robert is cheating.”
- Debbie assumes the opposite: “Robert is not cheating.”
- Contradiction: There are lewd texts on Robert’s phone (gasp), and we assume that “Robert is faithful” and “Robert sent saucy texts to the maid” can’t both be true at the same time. We assume that would be impossible.
- Result: Since assuming “Robert is not cheating” leads to a contradiction, the statement “Robert is not cheating” must be false. We instead conclude that the statement “Robert is cheating” is true.
This is also how proofs by contradiction work in math (although not with as much drama). We briefly assume the opposite of what we’re trying to prove, and then show that assuming the opposite leads to a contradiction.
Euclid’s Proof of Infinitely Many Primes
Euclid wanted to prove the following:
There are infinitely many prime numbers.
We’ll prove this with a proof by contradiction, so we’ll start by assuming the opposite:
There are finitely many prime numbers.
The above statement will lead to a paradox.
First, a brief note about prime numbers. You already know that a number is prime if it’s not divisible by any other number (other than itself or 1). I’m going to give you a slightly different but equivalent definition. A number is considered prime if it’s not divisible by any prime number other than itself. A number is not prime (aka composite) if it can be divided by some prime number other than itself.
Okay, back to the proof. If we assume the set of prime numbers is finite, then one of the prime numbers has to be the biggest. In general, any finite non-empty set of numbers has a largest number (example: if you have a finite number of friends, and you measure all of their heights, at least one friend has to be the tallest).
Let’s call the biggest prime number P. Now we’re going to multiply all the prime numbers together, and call that gigantic product N, like this:
2*3*5*7*11*…*P = N
N is certainly not prime. It’s divisible by 2, because N= 2*(3*5…*P). It’s also divisible by 3, because N=3*(2*5*7…*P). By definition, N is divisible by every prime number.
But what about N+1?
If you try to divide N+1 by 2, you will get a remainder of 1. N has a remainder of 0, since it’s divisible by 2, and 1 has a remainder of 1 when divided by 2, so N+1 has a remainder of 1.
If you try to divide N+1 by 3, you will also get a remainder of 1. In general, if you divide N+1 by any prime number, you will get a remainder of 1.
This means that N+1 is not divisible by any prime number, which means N+1 itself must be prime!
Clearly N+1 is a lot larger than P. However, we just showed that N+1 is prime, which would mean that P is not the largest prime. This is a contradiction: we defined P as “the biggest prime” but showed that it’s not the biggest prime after all. N+1 isn’t even the biggest prime either; we could repeat this process and find another prime larger than N+1.
Since assuming that there’s a largest prime leads to a contradiction, we have proven there can not be a largest prime number. If there’s no largest prime number, the set of prime numbers is infinite, and thus:
There are infinitely many prime numbers.
QED.
To Infinity and Beyond
There are lots of proofs of infinite primes besides Euclid’s. There are proofs from Leonhard Euler, Paul Erdős, Hillel Furstenburg, and many others. But Euclid’s is the oldest, and a clear example of a proof by contradiction, one of the most common types of proof in math.
By the way, the largest known prime (so far) is 2⁸²⁵⁸⁹⁹³³−1. If you wrote out that number, it would have 24,862,048 digits. If each digit was a person, the number would be the size of Shanghai. But thanks to Euclid, we know there are even larger primes out there in the universe.
