The *n*th Mersenne number is

*M*_{n} = 2^{n} – 1.

A Mersenne prime is a Mersenne number which is also prime. So far ~~50~~ 51 have been found [1].

A necessary condition for *M*_{n} to be prime is that *n* is prime, so searches for Mersenne numbers only test prime values of *n*. It’s not sufficient for *n* to be prime as you can see from the example

*M*_{11} = 2047 = 23 × 89.

## Lucas-Lehmer test

The largest known prime has been a Mersenne prime since 1952, with one exception in 1989. This is because there is an efficient algorithm, the Lucas-Lehmer test, for determining whether a Mersenne number is prime. This is the algorithm used by GIMPS (Great Internet Mersenne Prime Search).

The Lucas-Lehmer test is very simple. The following Python code tests whether *M*_{p} is prime.

def lucas_lehmer(p): M = 2**p - 1 s = 4 for _ in range(p-2): s = (s*s - 2) % M return s == 0

Using this code I was able to verify the first 25 Mersenne primes in under 50 seconds. This includes all Mersenne primes that were known as of 40 years ago.

## History

Mersenne primes are named after the French monk Marin Mersenne (1588–1648) who compiled a list of Mersenne primes.

Édouard Lucas came up with his test for Mersenne primes in 1856 and in 1876 proved that *M*_{127} is prime. That is, he found a 39-digit prime number by hand. Derrick Lehmer refined the test in 1930.

As of January 2018, the largest known prime is *M*_{77,232,917}.

## Related posts

[1] We’ve found 51 Mersenne primes as of December 22, 2018, but we’re not sure whether we’ve found the *first* 51 Mersenne primes. We know we’ve found the 47 smallest Mersenne primes. It’s possible that there are other Mersenne primes between the 47th and the 50th known Mersenne primes, and there may be one hiding between the 50th and 51st.