The nth Mersenne number is
Mn = 2n − 1.
A Mersenne prime is a Mersenne number which is also prime. So far 50 51 52 have been found.
A necessary condition for Mn 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
M11 = 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 Mp 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 M127 is prime. That is, he found a 39-digit prime number by hand. Derrick Lehmer refined the test in 1930.
As of October 21, 2024, the largest known prime is M136,279,841.
More prime number posts
Thank you very much for this explanation sir, simple and easy to understand. It helped me alot.