Mersenne primes

Mersenne primes are very intriguing. According to Mersenne a monk and mathematician all primes in the form
of 2^p  -1 where p prime as well, must be prime. We see this is true and not true for:

p=2 : 2²  -1 = 3 which is prime.
p=3 : 2³  -1 = 7 which is prime.
p=5 : 2⁵  -1 = 31 which is prime.
p=7 : 2⁷  -1 = 127 which is prime.
p=11 : 2¹¹  -1 = 2047 which is not prime. (Monks must be lazy !!)
p=13 : 2¹³  -1 = 8191 which is prime.
p=17 : 2¹⁷  -1 = 131071 which is prime.
p=19 : 2¹⁹  -1 = 524287 which is prime.
p= 23 : 2²³  -1 = 8388607 which is not prime.
p=29 : 2²⁹  -1 = 536870911 which is not prime.
p=31 : 2³¹  -1 = 2147483647 which is prime. And so on.

We see that not all of them are prime. Fact is that it is very easy to prove that
if p not prime that these numbers are composite. If however p prime it is not to say they are prime.
Some however are prime and these we call Mersenne primes if in the form 2^p  -1.
We also see that these numbers grow very quickly with increasing p.

So how do we test them for prime ness. In come Lucas and Lehmer with their very easy test.

Let S₀ = 4  then S_n+1  = S_n² - 2  mod M_p where M_p = 2^p  -1 with p prime. If S_p-2 = 0 then M_p is prime.

As example lets take p = 7, so M_p = 2^p  -1 = 2⁷  -1 = 127

So S₀ == 4
S₁ = S₀ ² - 2 =  16 -2 = 14 mod  127 = 14
S₂ = S₁ ² - 2 =  196 -2 = 194 mod 127 = 67
S₃ = S₂ ² - 2 =  4489 -2 = 4487 mod 127 = 42
S₄ = S₃ ² - 2 =  1764 -2 = 1762 mod 127 = 111 == -16
S₅ = S₄ ² - 2 =  256 -2 = 254 mod 127 = 0 , So M₇ = 127 is prime
We see that we arrive at the answer in 5 steps. Sort of 2 steps less than the exponent value of  M_p = 2^p  -1
This test is therefore quite fast if p big.

Currently (2007) there are only 44 Mersenne primes  known. The biggest prime of this sort founded so far is
M_p = 2^{32 582 657} - 1  . If you find such a prime, you will be famous and may also win some big money if it has more than 10 million digits.
This prime has 9 808 358 digits.

Back to Main Page