How many prime numbers are there?

“You can’t deal with my infinite nature.”

“That is so not true.  Wait, what does that even mean?”

So far, this blog has dealt with questions that are nontrivial to formulate but easy to answer.  Today I want to talk about a question about prime numbers which is not at all easy to answer.  Indeed, in many ways this is the starting point for the branch of mathematics where I live, number theory.

In number theory, we are especially interested in prime numbers.  (Quick and dirty definition in case it’s been a while: a prime number is an integer greater than 1 which cannot be written as a product of two integers greater than 1.)  The first few prime numbers are pretty easy to find just by trial and error.

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,\ldots$

So how many of these things are there?  Could we keep making this list as long as we want, or would we eventually run out of prime numbers?  In other words, which of the following alternatives is true?

Alternative A: There are infinitely many primes.  (There is no largest prime.)

Alternative B: There are only finitely many primes.  (There is a largest prime.)

I claim I know which of these statements is true and which is false.  I don’t just mean I have a persuasive guess, I mean I know.  One of those statements is right and one is wrong and there is no room for confusion about which is which.  Actually, this is a fundamental fact which should be known by any math major at any college in the world.

Notwithstanding what I just said, think about how preposterous it is to try to answer this question.  How could you ever know either of these things?  If you believe alternative A, then you have to believe that no matter how many prime numbers I have written down, you could find one larger than any of them.  If you believe alternative B, then you have to believe that there is a finite list of prime numbers, and no matter what number I say, however gigantic, all its prime factors are on the list.  Either way, we are claiming to know an infinite number of pieces of information.

You could get the faster supercomputer in the world to hunt for primes, but that wouldn’t help in the least.  No matter how many billion primes it found, that would be no guarantee there would be any more.  No matter how may years it went without finding another prime, that would be no guarantee it wouldn’t find one tomorrow.  So computational brute force is no good here.

It seems like a fool’s dream to want to settle the matter once and for all.  Nonetheless, we’ll answer it together after the cut.

In order to answer this question, we will need an observation about how prime factors work.  A prime factor of a number is just a prime number which can be divided into the number without a remainder.  The prime factors of 42 are 2, 3, and 7.  The prime factors of 1000000 are 2 and 5.

Observation 1. Every positive integer greater than 1 has at least one prime factor.

Why? Start with a positive integer $n>1$.  If $n$ is prime, then we found a prime factor; otherwise, we can write it as a product of smaller integers $n=n_1 n_2$, both greater than 1.   If $n_1$ or $n_2$ is prime, we found a prime factor.  Otherwise, we can break each of those up, $n = n_3 n_4 n_5 n_6$, all of them greater than 1.  Proceed in this way, at each stage either finding a prime factor (in which case we are happy) or decomposing the number further.  But the numbers involved are always integers greater than 1, and they get smaller with each decomposition.  It should be obvious that this can’t go on forever.

Why? (Colorful Alternative) Color all the integers greater than 1.  Color the ones that do have at least one prime factor red, and the ones that don’t blue.  It’s not obvious that there are any blue numbers at all.  If there are any blue numbers, pick out the smallest one and call it $n$.  The smallest blue number doesn’t have any prime factors (because it’s blue), so in particular it isn’t prime itself.  Thus we can write $n = n_1 n_2$ where $n_1,n_2$ are smaller integers greater than 1.  Since $n_1$ is smaller than the smallest blue number, it is red.  Since $n_1$ has a prime factor, so does $n$.  This is a problem, since $n$ was supposedly blue.  Thus there cannot be a smallest blue number.  All numbers are red.

(Actually, something much stronger than Observation 1 is true, the important-sounding Fundamental Theorem of Arithmetic.  More on that another day.)

First Proof.

Suppose for the sake of contradiction that Alternative B is the true one, that there is a largest prime number $p^\star$. Then consider the (extremely large) number $N= p^{\star}! +1$.  (See this post to be reminded what ! means.)  This number is almost too big to contemplate, but we still know some things about it.  For example it is odd, since it is one more than a multiple 2.  In fact, if you divide $N$ by any number less than or equal to $p^\star$, the remainder is 1.  So no number less than or equal to $p^\star$ can be a factor of $N$.  This is a serious problem, since all prime numbers are less than or equal to $p^\star$.  Thus $N$ can’t have any prime factors.

But this can’t be right, by Observation 1.  So that thing we assumed, Alternative B, must have been wrong.  The true alternative must be Alternative A.

So we have proven the following theorem, arguably the chronologically first real theorem of number theory.  Maybe the chronologically first real theorem of mathematics.

Theorem: There are infinitely many primes.

The proof just given is a classic.  It is the standard one given in textbooks, often attributed to Euclid, and of course it does the job.  But you might feel uncomfortable, or just aesthetically unsatisfied, with the reductio ad absburdum nature of the argument.  It’s rather mean-spirited of me to ask you to assume that alternative B is the true one, just to snatch it away and tell you it was alternative A after all.  We do not have to be so indirect.  I have another proof, less well-known, to offer.  We require another easy observation.

Observation 2. For any positive integers $m,n$, the numbers $m$ and $mn+1$ have no prime factors in common.

Why? Any prime factor of $m$ will go into $mn+1$ with remainder 1, so no number greater than 1 is simultaneously of a factor of both.

Second Proof.

Start with any integer greater than 1.  I’ll use 2, but the choice isn’t important.  Form an infinite sequence of numbers as follows.  The first number is the number you chose, and each number after that is the product of all the previous numbers, plus one.  If we start with 2, the sequence begins like this.

$2$

$2+1 = 3$

$2\times 3 + 1 =7$

$2\times 3\times 7 + 1 =43$

$2 \times 3\times 7 \times 43 +1 =1807$

and so on.

Now, each of these numbers has at least one prime factor (by Observation 1), but they can’t have any prime factors in common (Observation 2), so their prime factors include infinitely many different primes.

(Note that we are not saying that each number in the sequence is a larger prime, only that its prime factors are all primes we haven’t seen before.  In the example given $2, 3, 7, 43$ are all prime, so it’s natural to get your hopes up, but $1807 = 13 \times 139$.)