# The Hunt for Mersenne Primes

### Reference

Most of the material presented here can be found in the wonderful and very readable book
Joseph H. Silverman, A Friendly Introduction to Number Theory, Prentice-Hall, 1997.

### Prime Numbers

Definition: A positive integer is called a prime number, if it has exactly 2 divisors (1 and itself).

7 is prime, since 1 and 7 are the only divisors of 7.
15 is composite (not prime), since 15=3×5.
1 is not a prime number.
Here is a list of the first 100 prime numbers:

Theorem (Euclid): There are infinitely many prime numbers.

Proof.
Suppose   is a complete list of all prime numbers.
Consider Clearly is not divisible by any of the primes .
Either is a prime number itself (a contradiction; is not on the list . Why?), or is divisible by a number other than one of the listed primes, and thus divisible by a prime number not on the list , a contradiction as well.

Actually, both possibilities can occur. Here is the list of the first ten prime numbers:

Multiplying them and adding 1 yields a composite number, whose prime factors are not on the list:

This means 6469693231=331 × 571 × 34231.

The list of the first 11 prime numbers yields a prime number:

How rare are prime numbers?
More precisely, one can ask about the behavior of the function π(x), the number of prime numbers less than or equal to x.
Here is a plot of this function:

Gauss and Legendre both conjectured the following:

Prime Number Theorem (Hadamard and Vallee-Poussin, 1896):
For large
,   behaves asymptotically like the function .

Here is a plot of their quotient .

### Mersenne Primes

Here is a curious fact. If we consider small primes , -1 turns out to be prime, too:

What's wrong with this list? 11 is missing!

Definition:  A prime number of the form -1 is called a Mersenne prime.
In this case,
is called a Mersenne exponent.

Why are these numbers called Mersenne primes? Marin Mersenne boldly claimed in 1644 that a complete list of Mersenne exponents less than 258 is given by

Two of his conjectured exponents don't work; moreover he missed 89 and 107. Here is the correct list:

The fact that -1 is indeed prime, was proved by Lucas in 1876. The next Mersenne exponents were only found with the help of a computer by Robinson in 1952.

Let me list is a result we have already , at least partially, tacitly assumed:

Theorem: If -1 is prime, then =2 and is prime.

Proof.
I will only prove that -1 prime implies that is prime.
Assume that is not prime, then , with .
So -1 =  -1.
Do you remember how to factor -1? -1 "works" the same way:
-1 = -1) × ++ +1).
End of the story!  -1 is divisible by -1), and hence not prime.

### Perfect Numbers

Definition: A number is called perfect, if it equals the sum of its proper divisors.

6 and 28 are the smallest perfect numbers:

Now notice that × -1), and that 28 = × (-1). Is there a connection to Mersenne primes? You bet! Let's try this for the Mersenne prime -1:

It is in fact true, that every Mersenne prime yields a perfect number:

Theorem (Euclid): If -1 is prime, then -1) is perfect.

Proof.
Let's set -1. Note that is prime.
All we have to do is to sum up the proper divisors of × .
Here is a complete list of the proper divisors:
.
The geometric series formula tells us their sums:
= -1, and .
Thus the sum of the proper divisors of  × is given by
-1) + -1) = -1) × is a perfect number.

What about the converse? It is "half" true:

Theorem (Euler): If is an even perfect number, then -1) for some Mersenne prime

So, searching for even perfect numbers is equivalent to searching for Mersenne primes.
It is not known whether there are odd perfect numbers; there are none less than

### GIMPS

How many Mersenne primes are known? As of this date (March 1999) there are 37 known Mersenne primes.Their exponents are listed below:

 1 2 2 3 3 5 4 7 5 13 6 17 7 19 8 31 9 61 10 89 11 107 12 127 13 521 14 607 15 1279 16 2203 17 2281 18 3217 19 4253 20 4423 21 9689 22 9941 23 11213 24 19937 25 21701 26 23209 27 44497 28 86243 29 110503 30 132049 31 216091 32 756839 33 859433 34 1257787 35 1398269 36 2976221 37 3021377

Why do people hunt for Mersenne primes?
- Mersenne primes are usually the biggest primes known.
- Deciding whether -1 is a Mersenne prime, is relatively easy. In fact, Lehmer refined the procedure Lucas had used to determine whether 127 was a Mersenne exponent into what is known as the Lucas-Lehmer test for Mersenne numbers. It takes "only a few days" on a Pentium PC to test one exponent in the current range of interest.
- Everyone with spare computer time can join!

Welcome to GIMPS, the "reat Internet Mersenne Prime Search"!

The GIMPS status page.

### Etc.

Converted by Mathematica      April 26, 2003