Theorems About Mersenne Numbers
- 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.
- 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.
- 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.
- 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).
- 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.
- A prime number divides at most one prime-exponent Mersenne number
- 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.
- All composite divisors of prime-exponent Mersenne numbers pass the Fermat primality test for the base 2.
Read more about this topic: Mersenne Prime
Famous quotes containing the word numbers:
“Old age equalizeswe are aware that what is happening to us has happened to untold numbers from the beginning of time. When we are young we act as if we were the first young people in the world.”
—Eric Hoffer (19021983)
Main Site Subjects
Related Subjects
Related Phrases
Related Words