MaBloWriMo: Mersenne composites

The name of the game is to find Mersenne numbers $M_n = 2^n - 1$ which are also prime. Today, a simple observation: $M_n = 2^n - 1$ can only be prime when $n$ is also prime. Put conversely, if $n$ is composite then $M_n$ is also composite. For example, $4$ is composite and $M_4 = 2^4 - 1 = 15$ is also composite; $M_6 = 2^6 - 1 = 63$ is composite; and so on.

Why is this? We can actually give a very explicit proof that simply shows how to factor $M_n$ when $n$ is composite: if $n = pq$ , then

$2^{pq} - 1 = (2^p - 1)(2^{p(q-1)} + 2^{p(q-2)} + 2^{p(q-3)} + \dots + 2^p + 1)$ .

Can you see why? Multiplying $2^p$ by $2^{p(q-1)} + 2^{p(q-2)} + \dots + 1$ yields $2^{pq} + 2^{p(q-1)} + \dots + 2^p$ . If we then subtract $2^{p(q-1)} + 2^{p(q-2)} + \dots + 2^p + 1$ , everything cancels except the first $2^{pq}$ and the last $-1$ .

$\begin{array}{ccccccccccc} 2^{pq} &+& 2^{p(q-1)} &+& 2^{p(q-2)} &+& \dots &+& 2^p && \\ &-& 2^{p(q-1)} &-& 2^{p(q-2)} &-& \dots &-& 2^p &-& 1 \\ \hline 2^{pq} &&&&&&&&&-& 1 \end{array}$

So in fact, we can see that $M_{pq}$ must be evenly divisible by $M_p$ ; because $pq = qp$ , it must be evenly divisible by $M_q$ as well. So, for example, $M_4 = 15 = 3 \cdot 5$ is divisible by $M_2 = 3$ ; $M_6 = 63 = 7 \cdot 3^2$ is divisible by $M_3 = 7$ and $M_2$ ; $M_{10} = 1023 = 3 \cdot 11 \cdot 31$ is divisible by $M_5 = 31$ and $M_2$ .