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

Some examples are 3 = 2^{2}−1, 7 = 2^{3}−1, 31 = 2^{5}−1, and so on. Not all numbers of the form 2^{p}−1 are prime. For example, 2047 = 2^{11}−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^{n}−1 = (x−1)(x^{n−1} + x^{n−2} + ··· + 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^{n}−1, where n is an integer.

Source: wikipedia.org

Note: To prove the identity, we have

(x−1)(x^{n−1} + x^{n−2} + ··· + 1) = (x−1)Σ_{n−1}^{0}x^{k} = xΣ_{n−1}^{0}x^{k} − Σ_{n−1}^{0}x^{k}

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

xΣ_{n−1}^{0}x^{k} = Σ_{n−1}^{0}x^{k+1}

= Σ_{n}^{1}x^{k}

= x^{n} + Σ_{n−1}^{1}x^{k}

= x^{n} + Σ_{n−1}^{0}x^{k} − 1

Finally, we have (x−1)(x^{n−1} + x^{n−2} + ··· + 1) = xΣ_{n−1}^{0}x^{k} − Σ_{n−1}^{0}x^{k}

= x^{n} + Σ_{n−1}^{0}x^{k} − 1 − Σ_{n−1}^{0}x^{k} = x^{n}−1