## MaBloWriMo 4: not all prime-index Mersenne numbers are prime

Over the past couple days we saw that if $n$ is composite, then $M_n$ is also composite. Equivalently, this means that if we want $M_n$ to be prime, then at the very least $n$ must also be prime. But at this point there is an obvious question: is $M_n$ always prime when $n$ is prime? Or are there some prime $n$ for which $M_n$ is (sadly) composite?

Well, if $M_n$ were always prime whenever $n$ is prime, then I wouldn’t be writing this series of blog posts! That would be a nice, simple situation with no need for any fancy tests. But let’s see what actually happens:

• $M_2 = 3$ is prime.
• $M_3 = 7$ is prime.
• $M_5 = 31$ is prime.
• $M_7 = 127$ is prime.
• $M_{11} = 2047$ is… composite! $2047 = 23 \times 89$.

It turns out that $M_{13}$, $M_{17}$, and $M_{19}$ are all prime again, but then $M_{23}$ is not ( $2^{23} - 1 = 8388607 = 47 \times 178481$). And so on.

You get the idea: to find prime $M_n$, we only need to consider prime values of $n$. But even then we still have some checking to do, since not every prime $n$ corresponds to a prime Mersenne number $M_n$. In general, checking a number to see if it is prime can take a long time; the cool thing about Mersenne numbers is that using the Lucas-Lehmer test, we can check them for primality much more quickly than other numbers of a similar size. Tomorrow we’ll recall exactly how the Lucas-Lehmer test works, and try it on some small examples. 