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:

Table[Prime[i], {i, 100}]

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

Proof.
Suppose P = {(Subscript[p, 1]),(Subscript[p, 2]),(Subscript[p, 3]),....., (Subscript[p, n])}  is a complete list of all prime numbers.
Consider n = (Subscript[p, 1])(Subscript[p, 2])(Subscript[p, 3]).....(Subscript[p, n])+1. Clearly n is not divisible by any of the primes (Subscript[p, 1]),(Subscript[p, 2]),(Subscript[p, 3]),....., (Subscript[p, n]).
Either n is a prime number itself (a contradiction; n is not on the list P. Why?), or n is divisible by a number other than one of the listed primes, and thus divisible by a prime number not on the list P, a contradiction as well.

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

Table[Prime[i], {i, 10}]

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

n = Times@@% + 1

PrimeQ[n]

FactorInteger[n]

This means 6469693231=331 × 571 × 34231.

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

Table[Prime[i], {i, 11}]

n = Times@@% + 1

PrimeQ[n]

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:

\(\(p1 = 
      ListPlot[Table[{k, PrimePi[k]}, {k, 2, 10^6, 10^3}], 
	
        PlotJoined -> True, 
	PlotStyle -> {AbsoluteThickness[2], Red}]; 
    \)\)

Gauss and Legendre both conjectured the following:

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

Here is a plot of their quotient ((π (x))/(x/ln(x))).

\(\(\(p2 = 
      ListPlot[Table[{x, PrimePi[x]/\((x/Log[x])\)}, {x, 10^2, 10^6, 10^4}], 
        
		PlotJoined -> True, 
		
        PlotStyle -> {AbsoluteThickness[2], Blue}, 
		
        PlotRange -> {1, 1.2}]; \)
\)\)

Mersenne Primes

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

primes = {2, 3, 5, 7, 13, 17}

2^primes - 1

PrimeQ[%]

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

2^11 - 1

PrimeQ[2047]

Definition:  A prime number of the form (2^p)-1 is called a Mersenne prime. 
In this case, p 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

mersenne = {2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257}

2^mersenne - 1

PrimeQ[%]

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

\(\(		Select[Table[Prime[i], {i, 1, 55}], \((PrimeQ[2^# - 1])\)&]\)\)

The fact that (2^127)-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 (a^p)-1 is prime, then a=2 and p is prime.

Proof.
I will only prove that (2^p)-1 prime implies that p is prime.
Assume that p is not prime, then p  =  m × k, with m, k ≥ 2.
So (2^p)-1 =  ((((2^m)))^k)-1.   
Do you remember how to factor (x^3)-1? ((((2^m)))^k)-1 "works" the same way:
((((2^m)))^k)-1 = ((2^m)-1) × (  ((((2^m)))^(k - 1 ))+ ((((2^m)))^(k - 2 ))+ ((((2^m)))^(k - 3)) +....+ ((2^m)) +1).
End of the story!  (2^p)-1 is divisible by ((2^m)-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:

ProperDivisors[6]

ProperDivisors[28]

ProperDivisors[15]

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

n = 2^106 (2^107 - 1)

Short[ProperDivisors[n], 10]

Plus@@ProperDivisors[n]

Plus@@ProperDivisors[n] == n

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

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

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

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

Theorem (Euler): If n is an even perfect number, then n = (2^(p - 1)) ((2^p)-1) for some Mersenne prime (2^p) - 1.

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 (10^300) or so.

GIMPS

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

TableForm[Transpose[{Table[i, {i, 37}], known}], 
      TableAlignments -> Right]

\(merslist = Transpose[{Table[i, {i, 37}], Log[known]}]; 

    ListPlot[merslist, PlotStyle -> {Red, AbsolutePointSize[5]}, 
      AxesLabel -> {None, "natural log of the exponent"}]; \)

Why do people hunt for Mersenne primes?
- Mersenne primes are usually the biggest primes known.
- Deciding whether (2^p)-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 "Great Internet Mersenne Prime Search"!

The GIMPS status page.

Etc.

\(Needs["Graphics`Master`"]; 
Needs["Calculus`Master`"]; 

    ProperDivisors[n_Integer] := Drop[Divisors[n], \(-1\)]\)\(\(known
       = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 
		607, 1279, 
        2203, 2281, 3217, 4253, 4423, 9689, 9941, 
		11213, 19937, 21701, 
        23209, 44497, 86243, 110503, 132049, 
		216091, 756839, 859433, 
        1257787, 1398269, 2976221, 
		3021377}; \)\)

Helmut Knaust, email: helmut@math.utep.edu. Created 3-26-1999.