We now know that can only be prime when is prime; but even when is prime, sometimes is prime and sometimes it isn’t. The Lucas-Lehmer test is a way to tell us whether is prime, for any prime .

The test itself is actually straightforward, so I will just explain it quickly (if you want a more detailed explanation, along with some Haskell code, see my post from three years ago.

- Define .
- For each , define .
- Then is prime if and only if .

That is, start with , and at each step, square the current number, subtract two, and take the remainder when divided by . Do this times. is prime if you end with zero, and composite if you don’t.

Let’s do two small examples, one when is prime and one when it isn’t.

For , we get

so is prime. For , we get

so is not prime (though note this doesn’t really help us factor it!).

##
About Brent

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

Pingback: MaBloWriMo 6: The Proof Begins | The Math Less Traveled

The first sentence should have $M_n = 2^n – 1$ I believe. Anyway, this series of blog posts seems really nice. Thanks for that!

Thanks, fixed!