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.
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 4: not all prime-index Mersenne numbers are prime

  1. Pingback: MaBloWriMo 5: The Lucas-Lehmer Test | The Math Less Traveled

Comments are closed.