Mersenne Prime - About Mersenne Primes

About Mersenne Primes

Many fundamental questions about Mersenne primes remain unresolved. It is not even known whether the set of Mersenne primes is finite. The Lenstra–Pomerance–Wagstaff conjecture asserts that, on the contrary, there are infinitely many Mersenne primes and predicts their order of growth. It is also not known whether infinitely many Mersenne numbers with prime exponents are composite, although this would follow from widely believed conjectures about prime numbers, for example, the infinitude of Sophie Germain primes congruent to 3 (mod 4).

A basic theorem about Mersenne numbers states that in order for M_p to be a Mersenne prime, the exponent p itself must be a prime number. This rules out primality for numbers such as M₄ = 24 − 1 = 15: since the exponent 4 = 2×2 is composite, the theorem predicts that 15 is also composite; indeed, 15 = 3×5. The three smallest Mersenne primes are

M₂ = 3, M₃ = 7, M₅ = 31.

While it is true that only Mersenne numbers M_p, where p = 2, 3, 5, … could be prime - and it was believed by early mathematicians that all such numbers were prime - M_p is very rarely prime even for a prime exponent p. In fact, of the 1,509,263 prime numbers p up to 24,036,583, M_p is prime for only 41 of them. The smallest counterexample is the Mersenne number

M₁₁ = 211 − 1 = 2047 = 23 × 89,

which is not prime, even though 11 is a prime number. The lack of an obvious rule to determine whether a given Mersenne number is prime makes the search for Mersenne primes an interesting task, which becomes difficult very quickly, since Mersenne numbers grow very rapidly. The Lucas–Lehmer primality test (LLT) is an efficient primality test that greatly aids this task. The search for the largest known prime has somewhat of a cult following. Consequently, a lot of computer power has been expended searching for new Mersenne primes, much of which is now done using distributed computing.

Mersenne primes are used in pseudorandom number generators such as the Mersenne twister, Park–Miller random number generator, Generalized Shift Register and Fibonacci RNG.