The Hunt for Mersenne Primes

Marin Mersenne (1588-1648)


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.

Suppose [Graphics:Images/mersenne_gr_4.gif]  is a complete list of all prime numbers.
Consider [Graphics:Images/mersenne_gr_5.gif][Graphics:Images/mersenne_gr_6.gif] Clearly [Graphics:Images/mersenne_gr_7.gif] is not divisible by any of the primes [Graphics:Images/mersenne_gr_8.gif].
Either [Graphics:Images/mersenne_gr_9.gif] is a prime number itself (a contradiction; [Graphics:Images/mersenne_gr_10.gif] is not on the list [Graphics:Images/mersenne_gr_11.gif]. Why?), or [Graphics:Images/mersenne_gr_12.gif] is divisible by a number other than one of the listed primes, and thus divisible by a prime number not on the list [Graphics:Images/mersenne_gr_13.gif], 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
[Graphics:Images/mersenne_gr_30.gif],  [Graphics:Images/mersenne_gr_31.gif] behaves asymptotically like the function [Graphics:Images/mersenne_gr_32.gif].

Here is a plot of their quotient [Graphics:Images/mersenne_gr_33.gif].



Mersenne Primes

Here is a curious fact. If we consider small primes [Graphics:Images/mersenne_gr_36.gif] , [Graphics:Images/mersenne_gr_37.gif]-1 turns out to be prime, too:


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


Definition:  A prime number of the form [Graphics:Images/mersenne_gr_48.gif]-1 is called a Mersenne prime.
In this case,
[Graphics:Images/mersenne_gr_49.gif] 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 [Graphics:Images/mersenne_gr_58.gif]-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 [Graphics:Images/mersenne_gr_59.gif]-1 is prime, then [Graphics:Images/mersenne_gr_60.gif]=2 and [Graphics:Images/mersenne_gr_61.gif] is prime.

I will only prove that [Graphics:Images/mersenne_gr_62.gif]-1 prime implies that [Graphics:Images/mersenne_gr_63.gif] is prime.
Assume that [Graphics:Images/mersenne_gr_64.gif] is not prime, then [Graphics:Images/mersenne_gr_65.gif], with [Graphics:Images/mersenne_gr_66.gif].
So [Graphics:Images/mersenne_gr_67.gif]-1 =  [Graphics:Images/mersenne_gr_68.gif]-1.   
Do you remember how to factor [Graphics:Images/mersenne_gr_69.gif]-1? [Graphics:Images/mersenne_gr_70.gif]-1 "works" the same way:
[Graphics:Images/mersenne_gr_71.gif]-1 = [Graphics:Images/mersenne_gr_72.gif]-1) × [Graphics:Images/mersenne_gr_73.gif]+[Graphics:Images/mersenne_gr_74.gif]+[Graphics:Images/mersenne_gr_75.gif] [Graphics:Images/mersenne_gr_76.gif] +1).
End of the story!  [Graphics:Images/mersenne_gr_77.gif]-1 is divisible by [Graphics:Images/mersenne_gr_78.gif]-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 [Graphics:Images/mersenne_gr_85.gif]× [Graphics:Images/mersenne_gr_86.gif]-1), and that 28 = [Graphics:Images/mersenne_gr_87.gif] × ([Graphics:Images/mersenne_gr_88.gif]-1). Is there a connection to Mersenne primes? You bet! Let's try this for the Mersenne prime [Graphics:Images/mersenne_gr_89.gif]-1:


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

Theorem (Euclid): If [Graphics:Images/mersenne_gr_98.gif]-1 is prime, then [Graphics:Images/mersenne_gr_99.gif]-1) is perfect.

Let's set [Graphics:Images/mersenne_gr_100.gif]-1. Note that [Graphics:Images/mersenne_gr_101.gif] is prime.
All we have to do is to sum up the proper divisors of [Graphics:Images/mersenne_gr_102.gif]× [Graphics:Images/mersenne_gr_103.gif].
Here is a complete list of the proper divisors:
The geometric series formula tells us their sums:
[Graphics:Images/mersenne_gr_106.gif] = [Graphics:Images/mersenne_gr_107.gif]-1, and [Graphics:Images/mersenne_gr_108.gif].
Thus the sum of the proper divisors of  [Graphics:Images/mersenne_gr_109.gif]× [Graphics:Images/mersenne_gr_110.gif] is given by
[Graphics:Images/mersenne_gr_111.gif]-1) + [Graphics:Images/mersenne_gr_112.gif]-1) [Graphics:Images/mersenne_gr_113.gif] = [Graphics:Images/mersenne_gr_114.gif]-1) [Graphics:Images/mersenne_gr_115.gif][Graphics:Images/mersenne_gr_116.gif]× [Graphics:Images/mersenne_gr_117.gif] is a perfect number.

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

Theorem (Euler): If [Graphics:Images/mersenne_gr_118.gif] is an even perfect number, then [Graphics:Images/mersenne_gr_119.gif]-1) for some Mersenne prime [Graphics:Images/mersenne_gr_120.gif]

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 [Graphics:Images/mersenne_gr_121.gif]


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 [Graphics:Images/mersenne_gr_125.gif]-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 "[Graphics:Images/mersenne_gr_126.gif]reat Internet Mersenne Prime Search"!

The GIMPS status page.


Converted by Mathematica      April 26, 2003