The Hunt for Mersenne Primes

Marin Mersenne (1588-1648)

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:

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.