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!

TheoremThere 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 proof

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.

### Euler’s proof

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.

These are far from being the only proofs that there are infinitely many primes. You can read about some others on Wikipedia, or on the Prime Pages, for example.

November 3, 2009 at 9:37 am

A remark for a curious reader. The sum of the reciprocals of the squares can also be used to deduce infinitude of primes. Indeed is a consequence of unique factorization into primes and by the above. Since is transcendental, is irrational, and thus is not a product of finitely many prime numbers.

November 3, 2009 at 9:37 am

Typo: finitely many rational numbers

November 3, 2009 at 9:51 am

I haven’t seen (or thought of) that before, Boris. It’s brought a smile to my face — thanks!

February 16, 2010 at 10:20 pm

[…] By theoremoftheweek The fact that there are infinitely many prime numbers was a previous theorem of the week. This week, I’d like to pursue the idea a bit […]

October 7, 2011 at 12:50 pm

[…] Theorem 2: There are infinitely many prime numbers. We saw Euclid‘s proof. We’ll return to the subject of the distribution of the primes (and another proof that there are infinitely many primes) later in the course. […]

November 7, 2011 at 12:50 pm

[…] Proposition 44: For any , we have , where the sum is over all primes . We proved this by first showing that , and then that is bounded above by a constant (1/2, as it happens). […]

August 16, 2012 at 11:48 am

[…] Cantor, Cardano, Diophantus, Fermat, Galois, Tartaglia, Wiles. At some point we mentioned that there are infinitely many primes. We saw a special case of Fermat’s Little […]

August 15, 2013 at 9:12 am

[…] the week: Diophantus, Euler, Fermat, Germain, Riemann, Wiles. At some point we mentioned that there are infinitely many primes. We talked a little about the Twin prime conjecture, and about recent progress towards it; we […]

October 11, 2013 at 11:18 am

[…] Theorem 2: There are infinitely many primes. That is, as . Proof: Euclid‘s argument. […]

November 11, 2013 at 12:09 pm

[…] Proposition 43: For , we have . We considered . […]

January 25, 2015 at 9:18 pm

how can you prove that there is no positive prime numbers

March 8, 2015 at 4:35 am

Hey, I had a question that has been bugging me intensely about this: What about the product minus 1 instead of +1? Is there any consensus on whether or not that number can itself be prime?

March 8, 2015 at 11:44 am

Good question, Rick. It can go either way: it might be prime, it might not be. We can see that via some fairly small examples, e.g.

is prime

but is not prime.

But one less than the product isn’t divisible by any of the primes in the product, for the same reason that one more than the product isn’t, so we could just as well use that in Euclid’s proof.

Does that answer your question?

November 28, 2015 at 12:35 pm

[…] was proved by both Euclid (c.300BC) and Euler (18th century). This theorem of the week blog post gives some detail on […]

November 28, 2015 at 12:39 pm

[…] was proved by both Euclid (c.300BC) and Euler (18th century). This theorem of the week blog post gives some detail on […]