mersenne primes

Mersenne primes are prime numbers of the form 2^p−1, where p is prime. They are named after the French mathematician Marin Mersenne (1588-1648).

Some examples are 3 = 2²−1, 7 = 2³−1, and 31 = 2⁵−1. Not all numbers of the form 2^p−1 are prime. For example, 2047 = 2¹¹−1 = 23 * 89, is not prime.

For fun, we'll show that any number of the form 2^m−1, where m is a composite number, cannot be prime. That is, if a number of the form 2^m−1 is prime, then m is prime.

Proof: Let m = ab, where a and b are integers greater than 1. We use the identity xⁿ−1 = (x−1)(xⁿ⁻¹ + xⁿ⁻² + ··· + 1).

So we have 2^m−1 = 2^ab−1 = (2^a)^b−1, which is divisible by 2^a−1, and we are done.

Note: One consequence of the above result is that we could have defined a Mersenne prime equally well as any prime of the form 2ⁿ−1, where n is any integer.

Source: wikipedia.org

Note: To prove the identity, we have

(x−1)(xⁿ⁻¹ + xⁿ⁻² + ··· + 1) = (x−1)Σ_n−1⁰ x^k = xΣ_n−1⁰ x^k − Σ_n−1⁰ x^k

Let's examine more closely the first term of the final expression above:

xΣ_n−1⁰ x^k = Σ_n−1⁰ x^k+1

= Σ_n¹ x^k

= xⁿ + Σ_n−1¹ x^k

= xⁿ + Σ_n−1⁰ x^k − 1

Finally, we have (x−1)(xⁿ⁻¹ + xⁿ⁻² + ··· + 1) = xΣ_n−1⁰ x^k − Σ_n−1⁰ x^k

= xⁿ + Σ_n−1⁰ x^k − 1 − Σ_n−1⁰ x^k = xⁿ−1