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. See also [url=../notes/faq/NextMersenne.html]Where is the next larger
         Mersenne prime?[/url] and [url=heuristic.html]Mersenne heuristics[/url]
    
7. For remote pages on Mersennes see the Prime
       Links' Mersenne directory
   

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. [[url=../notes/proofs/EvenPerfect.html]Proof.[/url]]
 

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

 We put question marks instead of a number for the the last of the Mersenne
  primes because it will not be known if there are other Mersenne's in between
  these until a check and double check has been completed by GIMPS.  See
  the GIMPS Status Page for more information. 
  Not all smaller exponents have been tested.

4. The Lucas-Lehmer Test and Recent History

Lucas-Lehmer Test:  For p an odd prime, 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 the chair of their department, Dr. Bateman, had their postage meter changed
  to stamp "2¹¹²¹³-1 is prime" on each envelope.  This was used
  until the four color theorem was proved in 1976. (In 1985 Dr. Bateman printed
  several copies of the earlier imprint--the image on the left is from one of
  these.)

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 largest known Mersennes, 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 times 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  75 prime factors (not necessarily distinct [[url=../references/refs.cgi/Hare2006]Hare2006[/url]],
      [[url=../references/refs.cgi/Hare2005]Hare2005[/url]],
      [IS2003]) with at least 9 distinct [[url=../references/refs.cgi/Nielsen2006]Nielsen2006[/url]];
      it has at least 300 decimal digits [BCR91]; 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:
   

Theorem:  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. 
    See our page on [url=NewMersenneConjecture.html]The New Mersenne Conjecture[/url]
    for status information.

 

 Is every Mersenne number 2^p-1 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 [url=../notes/proofs/SquareMerDiv.html]easy
    to show[/url] 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 > 1051217599719369681875006054625051616349	(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.  Notice that if there is even one composite term in this
    sequences,  then by theorem one all of the following
    terms are composite. 
  (Landon Curt Noll tells
  me he has used his  program calc 
  to verify that C₅ has no prime divisors below 5*10⁵¹.)

 

 
 

Are there more double-Mersenne primes? 
 

Another common early misconception was that if n=M_p 
    is prime, then so is M_n; lets call this number MM_p 
    (a "double-Mersenne").  Indeed each of the first four such numbers are
    prime:
   

 MM₂  =  2³-1   =  7,

      MM₃  =  2⁷-1   =  127,

      MM₅  =  2³¹-1  =  2147483647,

      MM₇  =  2¹²⁷-1 =  170141183460469231731687303715884105727.
   

    However, the next four (MM₁₃ MM₁₇ MM₁₉ and
    MM₃₁) all have known factors--so are composite.  Are there
    any more primes in this sequence?  Probably not, but it remains an open
    question.  Tony Forbes is leading a
    project to search for a factor of the next term: MM₆₁, you
    might want to join and help!
   

Notice the Catalan sequence above is a subsequence of
      this one.