Editing Mersenne prime (section)

==Theorems about Mersenne numbers==
<!-- WARNING: you're NOT going to get a nice display by intermixing HTML-style lists with WIKIMEDIA-style markup within list items ! this has been tried !-->
Mersenne numbers are 0, 1, 3, 7, 15, 31, 63,&nbsp;... {{OEIS|id=A000225}}.

# If {{math|''a''}} and {{mvar|p}} are natural numbers such that {{math|''a<sup>p</sup>'' − 1}} is prime, then {{math|''a'' {{=}} 2}} or {{math|''p'' {{=}} 1}}.
#* '''Proof''': {{math|''a'' ≡ 1 ([[Modular arithmetic|mod]] ''a'' − 1)}}. Then {{math|''a<sup>p</sup>'' ≡ 1 (mod ''a'' − 1)}}, so {{math|''a<sup>p</sup>'' − 1 ≡ 0 (mod ''a'' − 1)}}. Thus {{math|''a'' − 1 {{!}} ''a<sup>p</sup>'' − 1}}. However, {{math|''a<sup>p</sup>'' − 1}} is prime, so {{math|''a'' − 1 {{=}} ''a<sup>p</sup>'' − 1}} or {{math|''a'' − 1 {{=}} ±1}}. In the former case, {{math|''a'' {{=}} ''a<sup>p</sup>''}}, hence {{math|''a'' {{=}} 0, 1}} (which is a contradiction, as neither −1 nor 0 is prime) or {{math|''p'' {{=}} 1.}} In the latter case, {{math|''a'' {{=}} 2}} or {{math|''a'' {{=}} 0}}. If {{math|''a'' {{=}} 0}}, however, {{math|0<sup>''p''</sup> − 1 {{=}} 0 − 1 {{=}} −1}} which is not prime. Therefore, {{math|''a'' {{=}} 2}}.
# If {{math|2<sup>''p''</sup> − 1}} is prime, then {{mvar|p}} is prime.
#* '''Proof''': Suppose that {{mvar|p}} is composite, hence can be written {{math|''p'' {{=}} ''ab''}} with {{mvar|a}} and {{math|''b'' > 1}}. Then {{math|2<sup>''p''</sup> − 1}} {{math|{{=}} 2<sup>''ab''</sup> − 1}} {{math|{{=}} (2<sup>''a''</sup>)<sup>''b''</sup> − 1}} {{math|{{=}} (2<sup>''a''</sup> − 1)<big>(</big>(2<sup>''a''</sup>)<sup>''b''−1</sup> + (2<sup>''a''</sup>)<sup>''b''−2</sup> + ... + 2<sup>''a''</sup> + 1<big>)</big>}} so {{math|2<sup>''p''</sup> − 1}} is composite. By contraposition, if {{math|2<sup>''p''</sup> − 1}} is prime then ''p'' is prime.
# If {{mvar|p}} is an odd prime, then every prime {{mvar|q}} that divides {{math|2<sup>''p''</sup> − 1}} must be 1 plus a multiple of {{math|2''p''}}. This holds even when {{math|2<sup>''p''</sup> − 1}} is prime.
#* For example, {{nowrap|2<sup>5</sup> − 1 {{=}} 31}} is prime, and {{nowrap|31 {{=}} 1 + 3 × (2 × 5)}}.  A composite example is {{nowrap|2<sup>11</sup> − 1 {{=}} 23 × 89}}, where {{nowrap|23 {{=}} 1 + (2 × 11)}} and {{nowrap|89 {{=}} 1 + 4 × (2 × 11)}}.
#* '''Proof''': By [[Fermat's little theorem]], {{mvar|q}} is a factor of {{math|2<sup>''q''−1</sup> − 1}}. Since {{mvar|q}} is a factor of {{math|2<sup>''p''</sup> − 1}}, for all positive integers {{math|''c''}}, {{mvar|q}} is also a factor of {{math|2<sup>''pc''</sup> − 1}}. Since {{mvar|p}} is prime and {{mvar|q}} is not a factor of {{nowrap|2<sup>1</sup> − 1}}, {{mvar|p}} is also the smallest positive integer {{mvar|x}} such that {{mvar|q}} is a factor of {{math|2<sup>''x''</sup> − 1}}. As a result, for all positive integers {{mvar|x}}, {{mvar|q}} is a factor of {{math|2<sup>''x''</sup> − 1}} if and only if {{mvar|p}} is a factor of {{mvar|x}}. Therefore, since {{mvar|q}} is a factor of {{math|2<sup>''q''−1</sup> − 1}}, {{mvar|p}} is a factor of {{math|''q'' − 1}} so {{math|''q'' ≡ 1 (mod ''p'')}}. Furthermore, since {{mvar|q}} is a factor of {{math|2<sup>''p''</sup> − 1}}, which is odd, {{mvar|q}} is odd. Therefore, {{math|''q'' ≡ 1 (mod 2''p'')}}.
#* This fact leads to a proof of [[Euclid's theorem]], which asserts the infinitude of primes, distinct from the proof written by Euclid: for every odd prime {{mvar|p}}, all primes dividing {{math|2<sup>''p''</sup> − 1}} are larger than {{mvar|p}}; thus there are always larger primes than any particular prime.
#* It follows from this fact that for every prime {{math|''p'' > 2}}, there is at least one prime of the form {{math|2''kp''+1}} less than or equal to {{mvar|M<sub>p</sub>}}, for some integer {{mvar|k}}.
# If {{mvar|p}} is an odd prime, then every prime {{mvar|q}} that divides {{math|2<sup>''p''</sup> − 1}} is congruent to {{nowrap|±1 (mod 8)}}.
#* '''Proof''': {{math|2<sup>''p''+1</sup> ≡ 2 (mod ''q'')}}, so {{math|2<sup>{{sfrac|1|2}}(p+1)</sup>}} is a square root of {{math|2 mod ''q''}}.  By [[quadratic reciprocity]], every prime modulus in which the number 2 has a square root is congruent to {{nowrap|±1 (mod 8)}}.
# A Mersenne prime cannot be a [[Wieferich prime]].
#* '''Proof''': We show if {{math|''p'' {{=}} 2<sup>''m''</sup> − 1}} is a Mersenne prime, then the congruence {{math|2<sup>''p''−1</sup> ≡ 1 (mod ''p''<sup>2</sup>)}} does not hold. By Fermat's little theorem, {{math|''m'' {{!}} ''p'' − 1}}.  Therefore, one can write {{math|''p'' − 1 {{=}} ''mλ''}}. If the given congruence is satisfied, then {{math|''p''<sup>2</sup> {{!}} 2<sup>''mλ''</sup> − 1}}, therefore {{math|0 ≡ {{sfrac|2<sup>''mλ''</sup> − 1|2<sup>''m''</sup> − 1}}}} {{math|{{=}} 1 + 2<sup>''m''</sup> + 2<sup>2''m''</sup> + ... + 2<sup>(''λ'' − 1)''m''</sup>}} {{math|≡ ''λ'' mod (2<sup>''m''</sup> − 1)}}. Hence {{math|p {{!}} ''λ''}}, and therefore {{math|1=−1 = 0 (mod p)}} which is impossible.
#If {{mvar|m}} and {{mvar|n}} are natural numbers then {{mvar|m}} and {{mvar|n}} are [[coprime]] if and only if {{math|2<sup>''m''</sup> − 1}} and {{math|2<sup>''n''</sup> − 1}} are coprime. Consequently, a prime number divides at most one prime-exponent Mersenne number.<ref>[http://www.garlic.com/~wedgingt/mersenne.html Will Edgington's Mersenne Page] {{webarchive|url=https://web.archive.org/web/20141014102940/http://www.garlic.com/~wedgingt/mersenne.html |date=2014-10-14 }}</ref> That is, the set of [[pernicious number|pernicious]] Mersenne numbers is pairwise coprime.
# If {{mvar|p}} and {{math|2''p'' + 1}} are both prime (meaning that {{mvar|p}} is a [[Sophie Germain prime]]), and {{mvar|p}} is [[Congruence relation|congruent]] to {{nowrap|3 (mod 4)}}, then {{math|2''p'' + 1}} divides {{math|2<sup>''p''</sup> − 1}}.<ref>{{cite web|url=http://primes.utm.edu/notes/proofs/MerDiv2.html|title=Proof of a result of Euler and Lagrange on Mersenne Divisors|first=Chris K.|last=Caldwell|work=[[Prime Pages]]}}</ref>
#* '''Example''': 11 and 23 are both prime, and {{nowrap|11 {{=}} 2 × 4 + 3}}, so 23 divides {{nowrap|2<sup>11</sup> − 1}}.
#* '''Proof''': Let {{mvar|q}} be {{math|2''p'' + 1}}. By Fermat's little theorem, {{math|2<sup>2''p''</sup> ≡ 1 (mod ''q'')}}, so either {{math|2<sup>''p''</sup> ≡ 1 (mod ''q'')}} or {{math|2<sup>''p''</sup> ≡ −1 (mod ''q'')}}. Supposing latter true, then {{math|2<sup>''p''+1</sup> {{=}} (2<sup>{{sfrac|1|2}}(''p'' + 1)</sup>)<sup>2</sup> ≡ −2 (mod ''q'')}}, so −2 would be a quadratic residue mod {{mvar|q}}. However, since {{mvar|p}} is congruent to {{nowrap|3 (mod 4)}}, {{mvar|q}} is congruent to {{nowrap|7 (mod 8)}} and therefore 2 is a quadratic residue mod {{mvar|q}}. Also since {{mvar|q}} is congruent to {{nowrap|3 (mod 4)}}, −1 is a quadratic nonresidue mod {{mvar|q}}, so −2 is the product of a residue and a nonresidue and hence it is a nonresidue, which is a contradiction. Hence, the former congruence must be true and {{math|2''p'' + 1}} divides {{mvar|M<sub>p</sub>}}.
# All composite divisors of prime-exponent Mersenne numbers are [[strong pseudoprime]]s to the base 2.
# With the exception of 1, a Mersenne number cannot be a perfect power. That is, and in accordance with [[Catalan's conjecture|Mihăilescu's theorem]], the equation {{math|2<sup>''m''</sup> − 1 {{=}} ''n<sup>k</sup>''}} has no solutions where {{mvar|m}}, {{mvar|n}}, and {{mvar|k}} are integers with {{math|''m'' > 1}} and {{math|''k'' > 1}}.
#The Mersenne number sequence is a member of the family of [[Lucas sequence|Lucas sequences]]. It is {{math|U<sub>''n''</sub>}}(3, 2). That is, Mersenne number {{math|''m''<sub>''n''</sub> {{=}} 3''m''<sub>''n''−1</sub> − 2''m''<sub>''n''−2</sub>}} with {{math|''m''<sub>0</sub> {{=}} 0}} and {{math|''m''<sub>1</sub> {{=}} 1}}.