As you might have already gathered from this blog, the prime numbers are pretty key in mathematics, and in particular in number theory (roughly speaking, the study of the whole numbers). (And since I’m a number theorist, I think they’re pretty cool!) The fundamental theorem of arithmetic (which says that every positive integer has a unique prime factorisation) tells us that they are the building blocks of the integers (if one builds by multiplying). And Goldbach’s conjecture (if true) and Vinogradov’s three primes theorem tell us interesting things about how the primes behave when we add them. But this all leaves some pretty fundamental questions unanswered. For example, how many primes are there?
It turns out that one can be fairly precise about how many primes there are, thanks to the prime number theorem (which I hope to make a future theorem of the week). For now, though, I’d like to discuss a simpler question: are there infinitely many primes?
It turns out that there are infinitely many primes. The Greek mathematician Euclid gave a famous proof of this fact, and I’d like to describe that proof here. But it’s not the only proof; I’ll also mention a proof by Euler that involves some rather interesting mathematics. Before that, I’ll state the theorem in a way that hopefully stands out!
Theorem There are infinitely many primes.
So, how could one go about proving a result like this? One important thing to notice is that we’re not trying to give a formula for the primes. It’s enough to prove the existence of infinitely many primes; we don’t have to give any way of listing them, or anything like that.
Euclid’s first idea was (in the modern way of presentation — he didn’t phrase it exactly like this) to use proof by contradiction. We are trying to prove that there is not a largest prime, and this is exactly the sort of (negative) statement for which proof by contradiction is so helpful.
So let’s suppose that there is a largest prime (and we then hope to make some deductions that lead to a contradiction). So we can write down all the primes, in a finite list. Say they’re , , , …, . So those are all the primes in the world.
Now comes Euclid’s second good idea, to generate a prime that isn’t on that list. He created a new number, , say, by multiplying together all those primes and adding . That is, .
What’s so special about this number? Well, it is a positive integer and so must have a prime factor. (This is a fact about positive integers that one has to prove. One can, for example, use induction.) But it cannot be divisible by any of the primes . Indeed, divides . So if divides , then it also divides — and that is clearly not possible.
So we have found a prime number (a prime factor of ) that is not any of our primes , …, . (Note that I’m not saying that itself is prime, but only that it has a prime factor.) But that contradicts our assumption that our list contained all prime numbers. That is the contradiction we were seeking, so our assumption (that there are only finitely many primes) must have been wrong. That is, there are infinitely many primes.
One can use similar ideas to show that there are infinitely many primes of the form . One has to work slightly harder, and one has to consider a slightly different number ( works well), but the ideas are broadly similar — you might like to think about the details.
I’m not going to give you all the details of Euler’s proof, for reasons that may become clear in a moment, but I’d like to give you the key idea. Euler considered the sum . (That is, it is the sum of the reciprocals of all the primes.)
Euler was able to prove that this sum diverges. That is, it is infinity. For comparison, you might like to know that the sum of the reciprocals of the natural numbers, , called the harmonic series, diverges, but the sum of the reciprocals of the squares, , converges — it is . (The alert reader will notice that once one knows that the sum of the reciprocals of the primes diverges, one immediately knows that the harmonic series diverges, because it’s bigger. But it’s also a lot easier to prove directly that the harmonic series diverges.) I’m not going to tell you about how to prove that the sum of the reciprocals of the primes diverges; that’s the bit of the proof that I’m skipping. If you’re interested, you could look at Wikipedia.
Why does the divergence of this sum prove that there are infinitely many primes? Well, suppose that there are only finitely many primes. Then the sum is a sum of finitely many things, so it is finite. But we know that the sum isn’t finite, so there must be infinitely many primes.
Once one has done the work to show the divergence of the sum of the reciprocals of the primes, the proof that there are infinitely many primes is very easy. In fact, the divergence of the sum gives more information: it gives some information about how many primes there are. For example, informally “there are more primes than squares”, because the sum of the reciprocals of the squares converges.