Mersenne Prime

A Mersenne number is an integer that is one less than a power of 2, i.e. it is of the form 2^n-1 where n is a positive integer. A Mersenne prime number (or a Mersenne prime) is a Mersenne number that happens to be a prime number. This post is a brief discussion on Mersenne prime.

Because Mersenne numbers are exponential, they increase very rapidly. The first several Mersenne numbers 2^n-1 starting with n = 2.

    3, 7, 15, 31, 63, 127, 255, 511, 1,023, 2,047, 4,095, 8,191, 16,383, 32,767, ……

It is clear from these examples that not all Mersenne numbers are prime (e.g. 15 and 63). In the above list, the numbers in red are prime and the ones in blue are composite. Note that the ones with composite exponent n are composite: 15 (n = 4), 63 (n = 6), 255 (n = 8), 511 (n = 9) …. This is no coincidence.

Whenever n is composite, the Mersenne number 2^n-1 is also composite.

The fact follows from the following identity.

    \displaystyle \begin{aligned} 2^{ab}-1&=(2^a-1) \ (1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}) \\&=(2^b-1) \ (1+2^b+2^{2b}+2^{3b}+\cdots+2^{(a-1)b})  \end{aligned}

Thus if we are interested in finding numbers 2^n-1 that are prime, we must start with an exponent n that is prime. For ease of discussion, define M_p=2^p-1 and assume that p is prime.

Mersenne primes have a long history. Long before the computer age, people had been doing primality testing on Mersenne numbers. The first four Mersenne primes M_p, for p = 2, 3, 5, and 7, were known in antiquity. The next Mersenne prime M_{13} was discovered before 1461. People at that time thought that M_p is prime whenever p is prime. In 1536, Hudalricus Regius found that M_{11}=2^{11}-1=2047=23 \times 89. In 1603, Pietro Cataldi showed that M_p is prime for p = 17 and 19.

The name of Mersenne prime was due to the connection with the French monk Marin Mersenne. In his 1644 book Cognita Physico-Mathematica, Mersenne stated that M_p is prime when p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257. Some of these claims were later determined to be wrong. His list also missed some correct Mersenne primes. From then on, his name was attached to this particular type of prime numbers.

The next discovery of a Mersenne prime (after Pietro Cataldi), M_{31}, was made by Leonhard Euler in 1772. The one found after Euler’s, M_{127}, was made by Edouard Lucas in 1876. There were three more Mersenne primes discovered before the computer age – M_{61} in 1883 by Ivan Pervushin, M_{89} and M_{107} by R. E. Powers in 1911 and 1914, respectively.

In the pre-computer age, there were long stretches of time in between discoveries of Mersenne primes. For example, it took almost 200 years after Pietro Cataldi for the next Mersenne prime to emerge (discovered by Euler). There were about 100 years in between Euler’s discovery and Lucas’ discovery.

Another important contribution made by Lucas is a test that he developed to test Mersenne numbers to see if they are prime. The test was originally developed in 1856 and later improved by him in 1878. It was further improved by Derrick Henry Lehmer in the 1930s. The test is now known as the Lucas-Lehmer test.

Lucas-Lehmer Test. Define a sequence of positive integers S_0, S_1, S_2, S_3, \cdots such that S_0=4 and S_j=S_{j-1}^2-2 where j \ge 1. Suppose that p \ge 3. Then M_p=2^p-1 is a Mersenne prime if and only if M_p divides S_{p-2}.

To perform the test, start with S_0=4 and recursively calculate S_j=S_{j-1}^2-2 until S_{p-2} is obtained. Then perform the division of S_{p-2} by M_p. If S_{p-2} is divisible by M_p, then M_p is prime. If S_{p-2} is not divisible by M_p, then M_p is composite. It is interesting that when M_p is found to be composite in this manner, the compositeness of M_p is established without finding any prime factors of M_p.

The computer discoveries of Mersenne primes began in 1952 by Raphael Robinson. The Lucas–Lehmer test is the primality test used by the Great Internet Mersenne Prime Search (GIMPS) to discover large primes. GIMPS is a distributed computing project on the Internet for finding large prime numbers.

As of the writing of this post (May 25, 2017), a total of 49 Mersenne primes had been discovered. The latest one is M_{74207281}, with over 22 million digits, which was found in January 2016.

Despite of the computation advance, there are still many fundamental questions that are still not known about Mersenne primes. For example, how many Mersenne primes are there? It is not even known whether the set of Mersenne primes is finite or infinite. It is also not known whether infinitely many Mersenne numbers with prime exponents are composite.

Because of the Lucas-Lehmer test, whenever someone finds a new largest prime number, it is usually a Mersenne prime. So every few years or so, Mersenne prime is on the news for the reason of being discovered. For up-to-date information or to learn more about basic facts, go to the Mersenne prime website and the Wikipedia entry on Mersenne primes.

\copyright 2017 – Dan Ma