# Prime Numbers: The “How many are there?” Edition

As you probably know, a prime number is a natural number like 2, 3, or 53, which is only evenly divisible by two numbes:  1 and itself.  The idea is that a prime number is a number which cannot be written as the product of two smaller numbers.  They act like the “atoms” of the natural numbers.  The Fundamental Theorem of Arithmetic says that every natural number can be written as a product of prime numbers in one and only one way.

It is easy to see that every number can be written as the product of primes by the following algorithm.  Take your number, if it’s prime you are done.  If not, then it can be written as the product of two smaller numbers.  Now repeat by applying the algorithm to the two smaller numbers.  You keep breaking down the factors into smaller and smaller pieces until you can’t anymore.  Once you can’t break any of the factors down further, then it means you have reached prime numbers.  The harder part of the theorem is to show that no matter how you do this, you end up with the same prime numbers.

Once you start thinking about prime numbers, you pretty quickly ask “How many are there?”  The short answer is “Infinitely many.”  The long answer is that there is a lot of different proofs for why there are infinitely many primes.  Why does anybody need more than one proof?  Because different proofs shed light on different aspects of the prime numbers and help us to better understand them.  Let’s look at a some of the different proofs of the fact that there is infinitely many primes below.

1. The oldest known proof is from Euclid‘s Elements from around 300 BC.  The proof is by contradiction:  Say that there is only a finite number of primes.  Let’s write them in a list from smallest to biggest:

$p_1, p_2, p_3, \dots, p_N,$

where N is the number of prime numbers.  Consider the number you get by multiplying them all together and adding 1:

$E=p_1 p_2 p_3 \cdots p_N + 1.$

If E is not divisible by any number other than itself and 1, then it is prime.  But E is bigger than any of the numbers in our list, so E would be a prime which is not in our list.  This contradicts our assumption that the list contains all primes.  So E is not prime.  This means we can write it as the product of two smaller numbers and, as we saw above, this means there is a prime number which divides E evenly.  Now the primes from our list $p_1, \dots, p_N$ do not divide E evenly since when you divide you get a remainder of 1.  So we have found a prime which is not on our list.  But this again contradicts our assumption that the list contained all primes.  Where did we go wrong?  By assuming that there was finitely many primes so that we could make the list in the first place!  Therefore there must be infinitely many primes.

This is a very nice and non-technical proof, and makes use of the fact that any number is either prime or is evenly divisible by a prime, which would suggest the Fundamental Theorem of Arithmetic to someone who didn’t already know about it.

Euclid in a painting by Raphael

2. Perhaps the newest proof uses the Green – Tao Theorem which we discussed here.  The Green – Tao Theorem was proven a few years ago and says that there are arbitrarily long arithmetic sequences in the primes.  The fact that there is infinitely many primes is a simple corollary of the theorem (we’ll let you think about why there has to be infinitely many primes if the Green – Tao Theorem is true).

It is cutting butter with a chainsaw to use the Green – Tao Theorem to prove that there is infinitely many primes, but this proof does bring a person’s attention to the arithmetic sequences in the primes.

Warning: We don’t know the details of the Green – Tao Theorem, and it may well use the fact that there is infinitely many primes in the proof itself.  Of course you are not allowed to use a fact to prove that same fact, so this proof might not be allowed!

3. The next proof uses the Mersenne numbers which we discussed here.  If there is finitely many prime numbers, then there is a largest prime number.  Let’s call it P.  Then consider the Mersenne number

$M = 2^P - 1.$

Observe that M is bigger than P.  If M is prime, then we have contradicted the assumption that P is the largest prime.  If M is not prime, we know that there is a prime number which divides M evenly.  Let’s call that prime q.  Since q divides M evenly, that means that $2^P$ equals 1 in the group of nonzero elements of $\mathbb{Z}_p$ with multiplication as the binary operation.  This means 2 has order P in this group.  But this group has q – 1 elements.  But by Legrange’s Theorem from group theory,  the order of an element of a group has to evenly divide the size of the group.  That means that P divides q-1 evenly.  Which means  $P \leq q-1$.  But that means P is smaller than q, contradicting our assumption that P was the biggest prime.  Where did we go wrong?  By assuming there was a biggest prime; that is, assuming that there was finitely many prime numbers.

The nice thing about this proof is that it points out the usefulness of the Mersenne Primes, using the size of natural numbers in proofs, and how you can use seemingly unrelated mathematics (like Legrange’s theorem) to prove the result you want.

Prime phone numbers in Toothpaste for Dinner

4. Another proof comes from a famous theorem called Bertrand’s Postulate. Bertrand’s postulate says that for any natural number n, there is a prime number between n and 2n.  It was conjectured by Bertrand after he checked all the numbers up to 3 million!  It was first proven by Chebyshev, then new proofs were given by Ramanujan and then by Erdos when he was only 19 years old!

This leads us to a famous quote by Nathan Fine pointed out to us by Dr. Forester:

Chebyshev said it, but I’ll say it again; There’s always a prime between n and 2n.

It’s easy to see that Bertrand’s Postulate implies there is infinitely many prime numbers.  But it also gives you some feeling for how spaced out the primes are.  It also suggests that the following result might be true:  for any positive integer k, there is a natural number N such that for all n > N, there are at least k primes between n and 2n.  This is true and was proven both by Ramanujan and Erdos.

A variation suggested by Bertrand’s Postulate is the still open Legendre’s Conjecture: Is there always a prime number between $n^2$ and $(n+1)^2$?  Nobody knows!

5. One of our favorite proofs that there is infinitely many primes is a consequence of the following Calc III type theorem.  It was first proven by Euler and then a different proof was given Erdos.  Let

$p_1, p_2, p_3, \dots$

be the list of prime numbers.  Consider the series

$\Sigma_{n \geq 1} \frac{1}{p_n} = 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + \cdots$

Euler and Erdos proved that this series diverges!

Of course this implies there is infinitely many primes since if there was only finitely many, then the above series would be a finite sum and so would converge.  But more than that, we know that the series

$\Sigma_{ n \geq 1} \frac{1}{n^2}$

converges, so roughly speaking we know that there is more primes then there is perfect squares!  So this theorem tells you something about how “many” primes there are.  That is, there is infinitely many primes and infinitely many perfect squares, but there is “more” primes.   Similar comparisions can be made with your other favorite converging or diverging series.

Euler on a German Stamp. Extra credit if you recognise the formula (Hint: Play-doh!).

6. There are many, many other proofs out there.  For example, the fact that there are infinitely many primes is an easy consequence of one of the most important open questions in mathematics, the Riemann hypothesis (By the way, in case you need to make some spare change, proving/disproving the Riemann hypothesis is one of the million dollar Millenium Prize Problems of the Clay Institute).

Amazingly, there is a topology proof that there is infinitely many primes!  It was given by Hillel Furstenberg and published in the Math Monthly while he was an undergraduate!  See here for the proof.

Stanislaw Ulam's Prime Spiral