The Corner

Everything You Need to Know About This Humongous Prime Number

OK, here’s the skinny on this business about the biggest prime number.

First off, there is no biggest prime number. The prime numbers go on for

ever. No matter how big a one you find, there’s a bigger one waiting out

there somewhere. What was turned up by this project was THE BIGGEST PRIME

WE HAVE SO FAR FOUND.

Second, it’s a Mersenne prime. That needs a bit of explanation.

Here are the first few primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,

41, 43, 47, 53, 59,… Notice that once you get past that starting “2,” all

the primes are odd numbers. Of course they are! A prime is defined to be a

number into which nothing divides (except 1 and itself). An even number can

be divided by 2, so it can’t be prime, unless it actually **is** 2.

Now, suppose I tell you to go find some prime numbers. Where are you going

to look? Well, you are going to look among the odd numbers. No point

looking among the even numbers.

Here’s a thing about odd numbers: an odd number–ANY odd number–differs

from an even number by just 1. To put it the other way round, if you start

with any even number, and add or subtract 1, you get an odd number.

So one possible strategy for finding primes would be: (1) think of some

interesting even numbers, (2) add 1 to each, to get an odd number–it might

be prime! Or: (3) subtract 1 from each, ditto ditto.

What is the most obvious class of even numbers? Why, the powers of 2. Here

are the first few: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,… Each

number is double the one to its left. These are the powers of 2. The

number 256, for instance, is 2×2×2×2×2×2×2×2, or “2 to the 8th power.” We

write it 2^8 for short.

These numbers are SERIOUSLY even. I mean, you can’t get any more even than

2×2×2×2x2x… So let’s add one to each, and see if we get any primes. Here

goes: 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049,… Writing “P” for

“prime” and “X” for “not prime,” these break out as: P, P, X, P, X, X, X,

P, X, X, X,… Hmmm. Didn’t do too well there.

Let’s try the other thing: SUBTRACTING 1 from powers of 2. Here we go: 1,

3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047,… These come out as: X, P,

P, X, P, X, P, X, X, X, P,…

Well, I’m getting SOME primes, anyway. But what are the patterns here?

Very early on in math history the following things were discovered:

(A) 2^n + 1 can only be a prime when “n” itself is a power of 2. In other

words, the only primes of this type are 2^2^n + 1. An example is 257, which

is 2^8 + 1, which is 2^2^3 +1. These are called FERMAT PRIMES, after the

great 17th-century French mathematician Pierre de Fermat

Note the word “can”: a number of the form 2^2^n + 1 does not have to be a

prime–when n=5, for example, it is not. It’s only that, if you want 2^n +

1 to be prime, you must have “n” equal to some power of 2.

(B) 2^n – 1 can only be a prime when “n” is itself a prime. An example is

2047, which is 2^11 – 1, since 11 is a prime. These primes are called

MERSENNE PRIMES, after another 17th-century Frenchman, the monk Marin

Mersenne

The word “can” applies here as before: 2^p – 1 does not need to be prime

(and in fact usually isn’t) even when “p” is a prime.

Because of the early discovery of these very particular kinds of primes, a

great body of knowledge about them has accumulated. This knowledge can be

used to find bigger and bigger instances. This is thus a well-established

way to go looking for big primes. These are of course very particular kinds

of primes. Most primes do not have the form 2^n – 1. It’s just that so

much work has been done on these types, that lots of techniques have

developed for spotting them.

Actually, this is only very profitable for Mersenne primes. Fermat primes

seem to be very rare. The number 2^2^n + 1 is prime when n = 0, 1, 2, 3, or

4 (values 3, 5, 17, 257, 65537) but no other cases are known. Nor is it

known whether there are any. I think most mathematicians believe there are

none when n > 4, but nobody has proved this.

With Mersenne primes, on the other hand, we now (as of last week) know 40.

There is a list here, with dates of discovery

http://www.utm.edu/research/primes/mersenne/index.html#known (go to heading

3). Notice how they have been turning up recently at the rate of slightly

less than one a year. One was discovered this year, one in 2001. In the

1990s, seven were found; in the 1980s, four, and in the 1970s also four.

Are there infinitely many Mersenne primes? Or will we eventually get to a

point beyond which there are no more to be found? Nobody knows.

Why should you care about any of this? You shouldn’t. These huge Mersenne

primes are of no practical value. (Big primes DO have a use in

cryptography, but those primes only have 60 or so digits. These recent

humongous discoveries, with MILLIONS of digits, are far too big for use in

cryptography.) You are not obliged to be interested in this stuff, any more

than you are obliged to be interested in symphonic music, or String Theory,

or synchronized swimming.

The question you might more profitably ask is: why do the people who care

about this care about it? The answer is the same as for symphonic music

etc.: viz. (a) because it is intrinsically beautiful–esthetically

pleasing, if you have been trained to appreciate that particular esthetic,

and (b) because it is fascinating to observe the very high level of

technical expertise of the best workers in this field.

Recommended

The Latest