Mersenne Primes:
History, Theorems and Lists

Contents:

1. Early History
2. Perfect Numbers and a Few Theorems
3. Table of Known Mersenne Primes
4. The Lucas-Lehmer Test and Recent History
5. Conjectures and Unsolved Problems
6. Remote pages on Mersennes:
   • Luke's Marin Mersenne page: Images, sounds, references, mailing list, software...
   • Summary of the Status of the Search for Mersenne Primes.
   • Mersenne Prime Freeware
   • Join the Great Internet Mersenne Prime Search -- maybe you will find the next prime?
   • Chris Nash's PriMers - Mersenne factoring in reverse
   • Will Edgington's Mersenne Primes
   • Landon Curt Noll's list of the decimal expansion of each known Mersenne as well as the English and European names of these numbers.

1. Early History

Enter French monk Marin Mersenne (1588-1648). Mersenne stated in the preface to his Cogitata Physica-Mathematica (1644) that the numbers 2ⁿ-1 were prime for

n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257 

Definition: When 2ⁿ-1 is prime it is said to be a Mersenne prime.

n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127.

2. Perfect Numbers and a Few Theorems

Definition: A positive integer n is called a perfect number if it is equal to the sum of all of its positive divisors, excluding n itself.

2^.3, 4^.7, 16^.31, 64^.127.

Theorem One: k is an even perfect number if and only if it has the form 2^n-1(2ⁿ-1) and 2ⁿ-1 is prime. [Proof.]

Theorem Two: If 2ⁿ-1 is prime, then so is n. [Proof.]

You may have also noticed that the perfect numbers listed above (6, 28, 496, 8128) all end with either the digit 6 or the digit 8--this is also very easy to prove (but no, they do not continue to alternate 6, 8, 6, 8,...). If you like that digit pattern, look at the first four perfect numbers in binary:

110
11100
111110000
1111111000000

When checking to see if a Mersenne number is prime, we usually first look for any small divisors. The following theorem of Euler and Fermat is very useful in this regard.

Theorem Three: Let p and q be primes. If q divides M_p = 2^p-1, then

q = +/-1 (mod 8)     and     q = 2kp + 1

for some integer k. [Proof.]

Theorem Four. Let p = 3 (mod 4) be prime. 2p+1 is also prime if and only if 2p+1 divides M_p. [Proof].

Theorem Five. If you sum the digits of any even perfect number (except 6), then sum the digits of the resulting number, and repeat this process until you get a single digit, that digit will be one. [Proof.]

3. Table of Known Mersenne Primes

It is not known if these last prime prime below is the 37th Mersenne prime as the region between them and the previous primes has not been completely tested. (Notice that the 29th Mersenne was found while scanning the region between two primes found five years earlier.)  GIMPS proved 2⁷⁵⁶⁸³⁹-1 is the 32nd (January 15, 1997), 2⁸⁵⁹⁴³³-1 is the 33rd (March 28, 1997), 2^1257787-1 is the 34th (August 28, 1997) and 2^1398269-1 is the 35th (October 11, 1997) by completing the tests for the remaining smaller exponents.  All exponents less than 1,481,800 have now been tested at least once.  See Mersenne Status for more current information (and how you may help).

4. The Lucas-Lehmer Test and Recent History

Lucas-Lehmer Test: For p odd, the Mersenne number 2^p-1 is prime if and only if 2^p-1 divides S(p-1) where S(n+1) = S(n)²-2, and S(1) = 4. [Proof.]

Lucas_Lehmer_Test(p):
  s := 4;
  for i from 3 to p do s := s2-2 mod 2p-1;
  if s == 0 then
    2p-1 is prime
  else
    2p-1 is composite;

In 1811 Peter Barlow wrote in his text Theory of Numbers that 2³⁰(2³¹-1) "is the greatest [perfect number] that will be discovered; for as they are merely curious, without being useful, it is not likely that any person will attempt to find one beyond it." I wonder what he would have made of the first attempts to climb Mount Everest, to run faster miles, or to jump a longer broad jump--other tasks that are curious but not useful. Obviously no one in the late 1800's had any idea of the power of modern computers. What might we know about the machines of 50 years from now? (See also "Why find big primes?")

After the 23rd Mersenne prime was found at the University of Illinois, the mathematics department was so proud that they had their postage meter changed to stamp "2¹¹²¹³-1 is prime" on each envelope.

The 25th and 26th Mersenne primes were found by high-school students Laura Nickel and Landon Curt Noll, who, though they had little understanding of the mathematics involved, used Lucas' simple test on the local university's mainframe (CSUH's CDC 174) to find the next two primes. Their discovery of the first prime made the national television news and the front page of the New York times. They went their separate ways after finding the first prime, but Noll kept the program running to find the second--so Noll claims complete ownership. Noll searched later, and though he never found another Mersenne prime, he is one of a team that holds the record for the largest non-Mersenne prime. He currently works for Silicon Graphics.

Slowinski, who works for Cray computers, has written a version of the Lucas test that he has convinced many Cray labs around the world to run in their spare time (time that would be lost otherwise). He had to delay announcing one of his prime records until he got permission to begin looking for it. Slowinski's search for record primes is "not so organized as you would suppose" (his words), as he does not search systematically. In fact, looking at the table of Mersennes you see he missed the 29th prime but found the 30th and 31st. Colquitt & Welsh worked to fill in the gaps and found the 29th.

Enter George Woltman, an excellent programmer and organizer. Starting in late 1995 he gathered up the disparate databases and combined them into one. Then he placed this database, and a free, highly optimized program for search for Mersennes onto the web. This began GIMPS (the Great Internet Mersenne Prime Search) which: has now found the three largest known Mersennes (via Clarkson, Armengaud and Spence), has scanned all of the regions left unexplored between the previous record primes, combines the efforts of dozens of experts and thousands of amateurs, and which offers free software for most computer platforms.

In late 1997 Scott Kurowski (and others) established PrimeNet to automate the selection of ranges and reporting of results for GIMPS, now almost anyone can join this search!

5. Conjectures and Unsolved Problems

Is there an odd perfect number? 

We know that all even perfect numbers are a Mersenne prime time a power of two (theorem one above), but what about odd perfect numbers? If there is one, then it is a perfect square times an odd power of a single prime; it is divisible by at least eight primes and has at least 29 prime factors (not necessarily distinct [Sayers86]); it has at least 300 decimal digits [BCR89]; and it has a prime divisor greater that 10²⁰ [Cohen87]. For more information see [Ribenboim95] or [Guy94].

Are there infinitely many Mersenne primes? 

Equivalently we could ask: Are there infinitely many even perfect numbers? The answer is probably yes (because the harmonic series diverges).

Are there infinitely many Mersenne composites? 

Euler showed:

If k>1 and p=4k+3 is prime, then 2p+1 is prime if and only if 2^p = 1 (mod 2p+1).

So if p=4k+3 and 2p+1 are prime then the Mersenne number 2^p-1 is composite (and it seems reasonable to conjecture that there are infinitely many primes pairs such p, 2p+1).

The New Mersenne Conjecture:

Bateman, Selfridge and Wagstaff have conjectured [BSW89] the following.

Let p be any odd natural number. If two of the following conditions hold, then so does the third:

1. p = 2^k+/-1   or   p = 4^k+/-3
2. 2^p-1 is a prime (obviously a Mersenne prime)
3. (2^p+1)/3 is a prime.

Notice how this conjecture is related to the theorem in the previous conjecture. This conjecture has been verified for all primes p<100,000.

Is every Mersenne number square free? 

This falls more in the category of an open question (to which we do not know the answer), rather than a conjecture (which we guess is true) [Guy94 section A3]. It is easy to show that if the square of a prime p divides a Mersenne, then p is a Wieferich prime and these are rare! Only two are known below 4,000,000,000,000 and neither of these squared divide a Mersenne.  

Let C₀ = 2, then let C₁ = 2^C₀-1, C₂ = 2^C₁-1, C₃ = 2^C₂-1, ... Are these all prime? 

According to Dickson [Dickson v1p22] Catalan responded in 1876 to Lucas' stating 2¹²⁷-1 (C₄) is prime with this sequence. These numbers grow very quickly:

C0 = 2	(prime)
C1 = 3	(prime)
C2 = 7	(prime)
C3 = 127	(prime)
C4 = 170141183460469231731687303715884105727	(prime)
C5 > 1051217599719369681879879723386331576246	(is C5 prime ?)

It seems very unlikely that C₅ (or many of the larger terms) would be prime, so this is no doubt another example of Guy's strong law of small numbers [Guy94]. (Landon Curt Noll tells me he has used his program calc to verify that C₅ has no prime divisors below 5^.10⁵⁰.)