Theorem 12: there are infinitely many primes

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 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 p_1p_2, p_3, …, p_k.  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, N, say, by multiplying together all those primes and adding 1.  That is, N = p_1 p_2 p_3 \dotsm p_k +1.

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 p_i.  Indeed, p_i divides p_1 p_2 p_3 \dotsm p_k.  So if p_i divides N, then it also divides 1 = N - p_1 p_2 p_3 \dotsm p_k — and that is clearly not possible.

So we have found a prime number (a prime factor of N) that is not any of our primes p_1, …, p_k.  (Note that I’m not saying that N 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 4n-1.  One has to work slightly harder, and one has to consider a slightly different number (N = 4p_1 p_2 \dotsm p_k -1 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 \sum_{p\textrm{ prime}} \frac{1}{p} = \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \frac{1}{13} + \dotsb.  (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, \sum_{n\geq 1} \frac{1}{n}, called the harmonic series, diverges, but the sum of the reciprocals of the squares, \sum_{n\geq 1} \frac{1}{n^2}, converges — it is \frac{\pi^2}{6}.  (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 \sum_{p\textrm{ prime}} \frac{1}{p} 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.

Advertisements

15 Responses to “Theorem 12: there are infinitely many primes”

  1. Boris Says:

    A remark for a curious reader. The sum of the reciprocals of the squares can also be used to deduce infinitude of primes. Indeed \prod (1-p^{-2})^{-1}=\sum 1/n^2 is a consequence of unique factorization into primes and \sum 1/n^2=\pi^2/6 by the above. Since \pi is transcendental, \pi^2/6 is irrational, and thus is not a product of finitely many prime numbers.

  2. Boris Says:

    Typo: finitely many rational numbers

  3. theoremoftheweek Says:

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

  4. Theorem 17: Dirichlet’s theorem « Theorem of the week Says:

    […] 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 […]

  5. Number Theory: Lecture 1 « Theorem of the week Says:

    […] 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. […]

  6. Number Theory: Lecture 14 « Theorem of the week Says:

    […] 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). […]

  7. Sutton Trust summer school 2012 « Theorem of the week Says:

    […] 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 […]

  8. Sutton Trust summer school 2013 | Theorem of the week Says:

    […] 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 […]

  9. Number Theory: Lecture 1 | Theorem of the week Says:

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

  10. Number Theory: Lecture 14 | Theorem of the week Says:

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

  11. okpa Says:

    how can you prove that there is no positive prime numbers

  12. Rick Says:

    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?

  13. theoremoftheweek Says:

    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.

    2 \times 3 \times 5 - 1 = 29 is prime

    but 2 \times 3 \times 5 \times 7 = 209 = 11 \times 19 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?

  14. Mathematics in Action | Mr Beckett's A Level Maths Says:

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

  15. Mathematics in Action | rbeckettyd Says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: