## 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$.

There is also a nice way to think of this in terms of binary numbers; I’ll explain that tomorrow.

## About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in algebra, arithmetic, computation, famous numbers, iteration, modular arithmetic, number theory, primes and tagged , , , , , , . Bookmark the permalink.

### 1 Response to MaBloWriMo: Mersenne composites

Comments are closed.