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.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →