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 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 50 Mersenne primes, but we’re not sure whether we’ve found the *first* 50 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 largest one currently known.