Are there infinitely many Mersenne primes?

[valeriob01]

Many fundamental questions about Mersenne primes remain unresolved. It is not even known whether the set of Mersenne primes is finite or infinite. The Lenstra–Pomerance–Wagstaff conjecture asserts that 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). For these primes p, 2p + 1 (which is also prime) will divide Mp, for example, 23 | M11, 47 | M23, 167 | M83, 263 | M131, 359 | M179, 383 | M191, 479 | M239, and 503 | M251 (sequence A002515 in the OEIS). Since for these primes p, 2p + 1 is congruent to 7 mod 8, so 2 is a quadratic residue mod 2p + 1, and the multiplicative order of 2 mod 2p + 1 must divide (2p+1)−1 = p. Since p is a prime, it must be p or 1. However, it cannot be 1 since Φ1(2)=1 and 1 has no prime factors, so it must be p. Hence, 2p + 1 divides Φp(2)=2p−1 and 2p−1=Mp cannot be prime.

The first four Mersenne primes are M2 = 3, M3 = 7, M5 = 31 and M7 = 127 and because the first Mersenne prime starts at M2, all Mersenne primes are congruent to 3 (mod 4). Other than M0 = 0 and M1 = 1, all other Mersenne numbers are also congruent to 3 (mod 4). Consequently, in the prime factorization of a Mersenne number ( ≥ M2 ) there must be at least one prime factor congruent to 3 (mod 4).

A basic theorem about Mersenne numbers states that if Mp is prime, then the exponent p must also be prime. This follows from the identity
2ab−1=(2a−1)⋅(1+2a+22a+23a+⋯+2(b−1)a)=(2b−1)⋅(1+2b +22b+23b+⋯+2(a−1)b).
This rules out primality for Mersenne numbers with composite exponent, such as M4 = 24 − 1 = 15 = 3 × 5 = (22 − 1) × (1 + 22).

Though the above examples might suggest that Mp is prime for all primes p, this is not the case, and the smallest counterexample is the Mersenne number
M11 = 211 − 1 = 2047 = 23 × 89.
The evidence at hand suggests that a randomly selected Mersenne number is much more likely to be prime than an arbitrary randomly selected odd integer of similar size.[2] Nonetheless, prime values of Mp appear to grow increasingly sparse as p increases. For example, eight of the first 11 primes p give rise to a Mersenne prime Mp (the correct terms on Mersenne's original list), while Mp is prime for only 43 of the first two million prime numbers (up to 32,452,843).

The lack of any simple test to determine whether a given Mersenne number is prime makes the search for Mersenne primes a difficult task, since Mersenne numbers grow very rapidly. The Lucas–Lehmer primality test (LLT) is an efficient primality test that greatly aids this task, making it much easier to test the primality of Mersenne numbers than that of most other numbers of the same size. 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.

Arithmetic modulo a Mersenne number is particularly efficient on a binary computer, making them popular choices when a prime modulus is desired, such as the Park–Miller random number generator. To find a primitive polynomial of Mersenne number order requires knowing the factorization of that number, so Mersenne primes allow one to find to primitive polynomials of very high order. Such primitive trinomials are used in pseudorandom number generators with very large periods such as the Mersenne twister, generalized shift register and Lagged Fibonacci generators.