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?”

— I Heart Huckabees

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.

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.

Think about which alternative you’re leaning toward before reading further.