Primes are a fascinating group of integer numbers. They definition is short and clear (a prime number is a number that can be divided without remainder only by itself and 1), there are infinite primes and “quite frequent” (for number of *n* digits they are about *n*/(log *n*), so one number every log *n* is prime).

Yet it is hard to prove deterministically the primality for a number of a large size, since algorithms have a polynomial execution time like O(*x*^{5}), so also a number of 70-80.000 digits is hard to prove prime.

This is not true for Mersenne Primes.

## Mersenne Primes

Mersenne Primes are prime numbers that are one unit smaller than a power of two; in general a Mersenne Number is a number with this form:

M* _{k}* = 2

^{k}– 1

and Mersenne Primes are the special case where both *k* and M* _{k}* are primes.

The first Mersenne Primes are:

2^{2}-1 = 3

2^{3}-1 = 7

2^{5}-1 = 31

2^{7}-1 = 127

2^{13}-1 = 8191

2^{11}-1 = 2047 = 23 * 89 is the first composite Mersenne Number with k prime, but in general as *k* grows Mersenne Prime become very sparse. Here the first 20 exponents:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423

It is easy to show that is *k* is not prime then M* _{k}* is not prime, in fact if

*k*=

*ab*:

\[ M_{ab} = 2^{ab} – 1 = (2^a – 1)(2^{(b-1)a} + 2^{(b-2)a} + \ldots + 2^a + 1) \]

Please note that in base 2 M* _{k}* is just

*k*“1” in a row. (3

_{10}= 11

_{2}, 7

_{10}= 111

_{2,}etc).

2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 |

31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 |

73 | 79 | 83 | 89 | 97 | 101 | 103 | 107 | 109 | 113 |

127 | 131 | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |

179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 | 229 |

233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 | 281 |

283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 | 349 |

353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 | 409 |

419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 | 463 |

467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 | 541 |

## Lucas-Lehmer Primality Test

Why is less hard to prove primality of these numbers? Because there is a particularly efficient primality test available for them: Lucas-Lehmer primality test. Please refer to Wikipedia for the algorithm, the important thing is that to prove primality of M* _{p}* = 2

^{p}-1=

*n*it is performed a cycle of about

*p*iteration (that is logarithmic in M

*(log*

_{p}*n*)), that perform multiplication of numbers (mod M

*) (so with size O(*

_{p}*n*). Ordinary multiplication would require O(

*n*

^{2}) operations for the multiplication, but using Fast Fourier Transform-based algorithms like Schönhage–Strassen algorithm we can compute it in O(

*n*log

*n*log log

*n*), so the total complexity is O(

*n*(log

*n*)

^{2}log log

*n*), tremendously faster than general purpose algorithms. In fact Mersenne primes hold the record of largest known primes since decades, the actually largest known prime is 2

^{82589933}− 1.

Actually only 51 Mersenne Primes have been found, mainly thanks to the GIMPS, a project that search Mersenne Primes during idle time of computers that join the project. It is unknown if they are infinite or if it exists a formula to easily find them.

## Perfect numbers

An interesting fact about Mersenne Primes is that they related to even perfect numbers. A perfect number is a number equal to the sum of its positive divisor except the number itself (e.g. 6 = 1+2+3, 28=1+2+3+4+7+14).

Euclid proved that is 2* ^{p}*-1 is prime than (2

^{p}-1)2

^{p-1}is perfect (this is easy, 2

*-1 has factors 1 and 2*

^{p}*-1, while 2*

^{p}^{p-1}has all the 2 powers from 0 to

*p*-1, just combine and sum them). Moreover Euler proved that all the even perfect number have this form.

The situation is still uncertain for odd perfect numbers. So far we don’t know if any exists, however some interesting fact is known, for example they should have at list 1500 digits and 10 different factors.

## Some open questions

Here some open questions more or less related to Mersenne Primes that deserve attentions if you like Mathematics.

Are there infinite many Mersenne Primes?

Are there a formula to compute *n*th Mersenne Prime?

Does exist an odd perfect number?

Now let’s raise the bar: consider the sequence of Mersenne Primes: 2, 3, 7, 127, they are each the exponent of the subsequent number:

- s
_{1}= 2^{2}-1 = 3 - s
_{2}= 2^{s1}-1 = 2^{3}-1 = 7 - s
_{3}= 2^{s2}-1 = 2^{7}-1 = 127 - s
_{4}= 2^{s3}-1 = 2^{127}-1 about 1.7 * 10^{38}

Is 2^{s4} – 1 prime? Is this the start of a sequence of prime numbers?

## Conclusions

This is just an introduction to the argument, I would like to write a post on the Schönhage–Strassen multiplication to use in a Lucas-Lehmer primality test implementation (probably preceded by a FFT post in code optimization section) and waste some time of mine on the above questions, but for now I just wanted to put this down as starting point.