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

Well, if were always prime whenever 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:

- is prime.
- is prime.
- is prime.
- is prime.
- is… composite! .

It turns out that , , and are all prime again, but then is not (). And so on.

You get the idea: to find prime , we only need to consider prime values of . But even then we still have some checking to do, since not every prime corresponds to a prime Mersenne number . 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

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

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