Editing Mersenne prime (section)

==About Mersenne primes==
{{unsolved|mathematics|Are there infinitely many Mersenne primes?}}
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]] claims that there are infinitely many Mersenne primes and predicts their [[asymptotic analysis|order of growth]] and frequency: For every number {{mvar|n}}, there should on average be about <math>e^\gamma\cdot\log_2(10) \approx 5.92</math> primes {{mvar|p}} with {{mvar|n}} decimal digits for which <math>M_p</math> is prime. Here, {{mvar|γ}} is the [[Euler–Mascheroni constant]]. 

It is also not known whether infinitely many Mersenne numbers with prime exponents are composite, although this would follow from widely believed [[conjecture]]s about prime numbers, for example, the infinitude of [[Sophie Germain prime]]s [[Congruence relation|congruent]] to 3 ([[Modular arithmetic|mod 4]]). For these primes {{mvar|p}}, {{math|2''p'' + 1}} (which is also prime) will divide {{mvar|M<sub>p</sub>}}, for example, {{math|23 {{!}} ''M''<sub>11</sub>}}, {{math|47 {{!}} ''M''<sub>23</sub>}}, {{math|167 {{!}} ''M''<sub>83</sub>}}, {{math|263 {{!}} ''M''<sub>131</sub>}}, {{math|359 {{!}} ''M''<sub>179</sub>}}, {{math|383 {{!}} ''M''<sub>191</sub>}}, {{math|479 {{!}} ''M''<sub>239</sub>}}, and {{math|503 {{!}} ''M''<sub>251</sub>}} {{OEIS|id=A002515}}. For these primes {{mvar|p}}, {{math|2''p'' + 1}} is congruent to 7 mod 8, so 2 is a [[quadratic residue]] mod {{math|2''p'' + 1}}, and the [[multiplicative order]] of 2 mod {{math|2''p'' + 1}} must divide <math display="inline">\frac{(2p+1)-1}{2} = p</math>. Since {{mvar|p}} is a prime, it must be {{mvar|p}} or 1. However, it cannot be 1 since <math>\Phi_1(2) = 1</math> and 1 has no [[prime factor]]s, so it must be {{mvar|p}}. Hence, {{math|2''p'' + 1}} divides <math>\Phi_p(2) = 2^p-1</math> and <math>2^p-1 = M_p</math> cannot be prime.
The first four Mersenne primes are {{math|1=''M''<sub>2</sub> = 3}}, {{math|1=''M''<sub>3</sub> = 7}}, {{math|1=''M''<sub>5</sub> = 31}} and {{math|1=''M''<sub>7</sub> = 127}} and because the first Mersenne prime starts at {{math|''M''<sub>2</sub>}}, all Mersenne primes are congruent to 3 (mod 4). Other than {{math|1=''M''<sub>0</sub> = 0}} and {{math|1=''M''<sub>1</sub> = 1}}, all other Mersenne numbers are also congruent to 3 (mod 4). Consequently, in the [[prime factorization]] of a Mersenne number (&nbsp;{{math|&ge; ''M''<sub>2</sub>}}&nbsp;) there must be at least one prime factor congruent to 3 (mod 4).

A basic [[theorem]] about Mersenne numbers states that if {{mvar|M<sub>p</sub>}} is prime, then the exponent {{math|''p''}} must also be prime. This follows from the identity
<math display="block">\begin{align}
2^{ab}-1
&=(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}\right)\\
&=(2^b-1)\cdot \left(1+2^b+2^{2b}+2^{3b}+\cdots+2^{(a-1)b}\right).
\end{align}</math>
This rules out primality for Mersenne numbers with a composite exponent, such as {{math|1=''M''<sub>4</sub> = 2<sup>4</sup> − 1 = 15 = 3 × 5 = (2<sup>2</sup> − 1) × (1 + 2<sup>2</sup>)}}.

Though the above examples might suggest that {{mvar|M<sub>p</sub>}} is prime for all primes {{mvar|p}}, this is not the case, and the smallest counterexample is the Mersenne number

: {{math|1=''M''<sub>11</sub> = 2<sup>11</sup> − 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.<ref name="Wagstaff">{{cite web| url=http://primes.utm.edu/mersenne/heuristic.html|title=Heuristics: Deriving the Wagstaff Mersenne Conjecture| first=Chris|last=Caldwell}}</ref> Nonetheless, prime values of {{mvar|M<sub>p</sub>}} appear to grow increasingly sparse as {{mvar|p}} increases. For example, eight of the first 11 primes {{mvar|p}} give rise to a Mersenne prime {{mvar|M<sub>p</sub>}} (the correct terms on Mersenne's original list), while {{mvar|M<sub>p</sub>}} is prime for only 43 of the first two million prime numbers (up to 32,452,843).

Since Mersenne numbers grow very rapidly, the search for Mersenne primes is a difficult task, even though there is a simple efficient test to determine whether a given Mersenne number is prime: the [[Lucas–Lehmer primality test]] (LLT), which makes 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]].{{Citation needed|date=May 2023}} Consequently, a large amount 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 number|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 (field theory)|primitive polynomial]] of Mersenne number order requires knowing the factorization of that number, so Mersenne primes allow one to find primitive polynomials of very high order.  Such [[primitive polynomial (field theory)#Primitive trinomials|primitive trinomials]] are used in [[pseudorandom number generator]]s with very large periods such as the [[Mersenne twister]], generalized shift register and [[Lagged Fibonacci generator]]s.