Mersenne Prime - Theorems About Mersenne Numbers

Theorems About Mersenne Numbers

1. If a and p are natural numbers such that ap − 1 is prime, then a = 2 or p = 1.
   • Proof: a ≡ 1 (mod a − 1). Then ap ≡ 1 (mod a − 1), so ap − 1 ≡ 0 (mod a − 1). Thus a − 1 | ap − 1. However, ap − 1 is prime, so a − 1 = ap − 1 or a − 1 = ±1. In the former case, a = ap, hence a = 0,1 (which is a contradiction, as neither 1 nor 0 is prime) or p = 1. In the latter case, a = 2 or a = 0. If a = 0, however, 0p − 1 = 0 − 1 = −1 which is not prime. Therefore, a = 2.
2. If 2p - 1 is prime, then p is prime.
   • Proof: suppose that p is composite, hence can be written p = a⋅b with a and b > 1. Then (2a)b − 1 is prime, but b > 1 and 2a > 2, contradicting statement 1.
3. If p is an odd prime, then any prime q that divides 2p − 1 must be 1 plus a multiple of 2p. This holds even when 2p − 1 is prime.
   • Examples: Example I: 25 − 1 = 31 is prime, and 31 = 1 + 3×2×5. Example II: 211 − 1 = 23×89, where 23 = 1 + 2×11, and 89 = 1 + 4×2×11.
   • Proof: If q divides 2p − 1 then 2p ≡ 1 (mod q). By Fermat's Little Theorem, 2(q − 1) ≡ 1 (mod q). Assume p and q − 1 are relatively prime, a similar application of Fermat's Little Theorem says that (q − 1)(p − 1) ≡ 1 (mod p). Thus there is a number x ≡ (q − 1)(p − 2) for which (q − 1)·x ≡ 1 (mod p), and therefore a number k for which (q − 1)·x − 1 = kp. Since 2(q − 1) ≡ 1 (mod q), raising both sides of the congruence to the power x gives 2(q − 1)x ≡ 1, and since 2p ≡ 1 (mod q), raising both sides of the congruence to the power k gives 2kp ≡ 1. Thus 2(q − 1)x/2kp = 2(q − 1)x − kp ≡ 1 (mod q). But by definition, (q − 1)x − kp = 1, implying that 21 ≡ 1 (mod q); in other words, that q divides 1. Thus the initial assumption that p and q − 1 are relatively prime is untenable. Since p is prime q − 1 must be a multiple of p. Of course, if the number m = (q − 1)⁄_p is odd, then q will be even, since it is equal to mp + 1. But q is prime and cannot be equal to 2; therefore, m is even.
   • Note: This fact provides a proof of the infinitude of primes distinct from Euclid's Theorem: if there were finitely many primes, with p being the largest, we reach an immediate contradiction since all primes dividing 2p − 1 must be larger than p.
4. If p is an odd prime, then any prime q that divides must be congruent to ±1 (mod 8).
   • Proof:, so is a square root of 2 modulo . By quadratic reciprocity, any prime modulo which 2 has a square root is congruent to ±1 (mod 8).
5. A Mersenne prime cannot be a Wieferich prime.
   • Proof: We show if p = 2m - 1 is a Mersenne prime, then the congruence 2p - 1 ≡ 1 does not satisfy. By Fermat's Little theorem, . Now write, . If the given congruence satisfies, then ,therefore 0 ≡ (2mλ - 1)/(2m - 1) = 1 + 2m + 22m + ... + 2λ-1m ≡ -λ mod(2m - 1}. Hence ,and therefore λ ≥ 2m − 1. This leads to p − 1 ≥ m(2m − 1), which is impossible since m ≥ 2.
6. A prime number divides at most one prime-exponent Mersenne number
7. If p and 2p+1 are both prime (meaning that p is a Sophie Germain prime), and p is congruent to 3 (mod 4), then 2p+1 divides 2p − 1.
   • Example: 11 and 23 are both prime, and 11 = 2×4+3, so 23 divides 211 − 1.
8. All composite divisors of prime-exponent Mersenne numbers pass the Fermat primality test for the base 2.