Mersenne Primes and Perfect Numbers

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(x5), 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:

Mk = 2k – 1

and Mersenne Primes are the special case where both k and Mk are primes.

The first Mersenne Primes are:

22-1 = 3

23-1 = 7

25-1 = 31

27-1 = 127

213-1 = 8191

211-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 Mk 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 Mk is just k “1” in a row. (310 = 112, 710 = 1112, etc).

Distribution of exponents of first Mersenne Primes in prime numbers

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 Mp = 2p-1= n it is performed a cycle of about p iteration (that is logarithmic in Mp (log n)), that perform multiplication of numbers (mod Mp) (so with size O(n). Ordinary multiplication would require O(n2) 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 282589933 − 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 2p-1 is prime than (2p-1)2p-1 is perfect (this is easy, 2p-1 has factors 1 and 2p-1, while 2p-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 nth 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:

  • s1= 22-1 = 3
  • s2 = 2s1-1 = 23-1 = 7
  • s3 = 2s2-1 = 27-1 = 127
  • s4 = 2s3-1 = 2127-1 about 1.7 * 1038

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


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.