No largest prime

NEW:  due to popular demand, I have gone ahead and posted a list of all the prime numbers.

There is no largest prime number.

Suppose there is a largest prime number.  Then you can make a list of all the prime numbers, and that list does not go on forever (it is finite).  Any number greater than 1 and not on your list must divide by something that is on the list.  Take all the prime numbers, multiply them together, and add one.  The resulting number does not divide by any of the numbers on your list; therefore, it must be prime.  But that contradicts what we said earlier, which was that your list had all the prime numbers on it.  So such a list cannot exist.

Therefore, there is no largest prime number.

Comments

Of course, that proof is aimed at lay people, which is why I didn't use formal mathematical language.  If you think you're a real mathematician and email me to pick nits about my choice of which points to gloss over, or what bits are insufficiently rigorous, I'll just ignore it.

Some people are skeptical of this proof because they have a vague idea that it's difficult to find an infinite sequence of prime numbers and they say, "Well, if this procedure of multiplying them all together and adding one always gives you a prime number, then why can't you just keep doing it and generate all the primes?" There are two problems with that idea.

First of all, the multiply-and-add-one procedure doesn't really guarantee to generate a prime.  It only guarantees to generate a number that doesn't divide by any of the numbers on your list.  That's good enough for the proof, because the proof assumes that all primes are on the list and so anything that doesn't divide by any of them must not divide by anything at all and so must be prime.  But in fact, the procedure could generate a number that is not prime, but divides by some prime not on your list.  Let's say your prime list is complete up to 13.

Your list should read:  2, 3, 5, 7, 11, 13.
2 x 3 x 5 x 7 x 11 x 13 = 30030.
Add 1, you get 30031.
But 30031 = 59 x 509, so it's not prime.
The procedure doesn't always generate primes.

As if that weren't bad enough, even if the multiplying procedure did always generate primes, it doesn't necessarily generate the next prime, so you can't apply it repeatedly without missing the vast majority of primes.  In fact, it never generates the next prime unless your list is just the number 2.  So you don't get very far:  2 times 3 is 6, add 1 you get 7 which is prime, but 5 is prime too and you've missed it.  If you go another step just using 2, 3, and 7, you get 43, which is a prime so you're okay, but after that you get 1807, which equals 13 times 139.

Special note for smartass Grade 5 students

I was once like you, and like you I said But hey, you can divide any number by any other number, you just get a fraction. That's true as far as it goes, but there are a few things you have to understand.

Zeroth of all, you can't divide by just any number, it has to be any number except zero.  Ha ha, got you.

Then first of all, keep it to yourself.  It doesn't make people happy when they find out that you're smarter than them.  It's enough to know that you know the teacher is wrong; you don't have to let the teacher know that you know they're wrong.  Believe me, I've been there and I know what I'm talking about, and the earlier you learn this lesson the happier you'll be.

Second of all, and more important, mathematics is just a bunch of games with rules.  Often mathematicians make up their own rules.  In Grade 5 they don't tell you that - they tell you that two plus two equals four like it was some sort of fundamental law of nature.  When you learn about modulo arithmetic you'll discover that it's perfectly sensible to say instead that two plus two equals one (modulo three) - that should technically be is congruent to one but everyone will know what you mean.  Or you can make it be equal to zero, or seven, or ninety-nine, or the square root of yellow, as long as you and whoever you're playing math with can agree on the right rules.

Where is this leading?  Well, when people talk about primes, that usually means they're playing the mathematical game called Number Theory.  And in Number Theory, one of the rules is no fractions.  If you can't divide without fractions, you're not allowed to divide at all.  Now, remember, that's only in the Number Theory game.  You can play a different game (like the Rational Algebra game) and fractionate to your heart's content.  You can even play with real numbers, where you get things that are sort of fractions but can't be made by dividing whole numbers.  (The number called pi is one of those irrational numbers.  3.14159 26535 89793...) But when we're talking primes and we say divide, we almost always mean divide evenly, with no fractions or remainder.

Another rule of number theory is that we only use positive numbers, so don't spend too much time worrying about how to get to -15 when you don't have any negative primes.  (-15 isn't even greater than 1 anyway, and in the proof I said it had to be numbers greater than 1.)

But it is a good sign if you're noticing things like Hey, wait a minute, I can divide by any number.  Most people who say that in Grade 5 grow up to be good mathematicians if they want to, or good other things.

Comments

Copyright © 1999,2003 Matthew Skala
Updates to this entire site:
Updates to this category (teebee) only: