# Mersenne Primes

**Marin Mersenne** (1588-1648) was a Franciscan friar who lived most of
his life in Parisian cloisters. He was the author of *Cognitata
Physico-Mathematica* which stated without proof that M*p* is
prime for *p* = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257 and
for no other primes *p* for *p* < 257. It took over 300
years to totally settle this claim made by Mersenne. The final work
done in 1947 showed that Mersenne made five errors in his work (namely
that M*61* is prime, M*67* is composite, M*89* is prime,
M*107* is prime, and M*257* is composite). Besides his
famous statement about primes of the form M*p*, Mersenne
contributed to the development of number theory through his extensive
correspondence with many mathematicians, including Fermat. Mersenne
effectively served as a clearing house and a disseminator of new
mathematical ideas in the 17th century.
*Kenneth Rosen, Elementary Number Theory; Addison Wesley*

The concept of a Mersenne Prime is evolved from that of a
*perfect number*. A *perfect number* is an integer
for which the sum of its divisors is twice the number. For example:

(6) = 1 + 2 + 3 + 6 = 12 = 2*6
thus 6 is a perfect number.

The greeks discovered that all perfect numbers were of the form:

n = 2^(m-1) * (2^m - 1)
where m >= 2 and (2^m - 1) is prime.

It can be proven that if *m* is a positive integer and
2^*m* - 1 is prime, that *m* must be prime. This
means that the quest for perfect numbers is reduced to the quest
for primes of the form:
2^*m* - 1

A *Mersenne Prime* is such a number M*p*, where p is prime.
A *Mersenne Number* is a number M*m* which may or may not be prime.

There are additional theorems which can be used to determine
properties of Mersenne Numbers. One states:

If *p* is an odd prime, then any divisor of
the Mersenne number M*p* = 2^*p* - 1 is of the
form 2*kp* + 1 where *k* is a positive integer.

This leads instantly to a method of testing the primality of M*p*.
We know that any prime factors must be less than the square root, and
we know from above that they must be of the form 2*kp* + 1.
This is likely the method used by Mersenne to determine the primality
of the Mersenne numbers for *m* < 257.

## The Lucas-Lehmer Test

*I don't know anything about the development of this algorithm,*
Let *p* be a prime and M*p* = 2*p* - 1 the *p*th
Mersenne number. Then define a recursive sequence by setting R*1* = 4,
and *k* >= 4,

R*k* = (R*k-1*)^2 - 2 (mod M*p*),
for 0 <= R*k* < M*p*.

Then M*p* is prime if and only if R*p-1* = 0 (mod M*p*).
In pseudo code,

R = 4;
for (i = 2; i > *p*; i++) {
R = R*R;
R -= 2;
R = R mod M*p*
}
if (R == 0)
M*p* is prime

In practice this is limited by the O(N^2) cost of multiplication.
The technique used to evade this cost is to use FFTs to do your
multiplication for you. *I still don't ***really** understand
how that works.

## Known Mersenne Primes

There are currently 33 known Mersenne Primes. The upper limits are
reserved to those with more supercomputer power than is good for humans
to possess. They seem to be discovered every two years or so.
List the numbers here

banshee@resort.com
**Your links back to The Resort**

Resort Home Page
| Meet the Resort
| Photo Gallery
| Services
| Whats New?
| Feedback

All Contents Copyright 1992-1997 by *The Resort* . Give us food,
money, beer, or kill us.