MaBloWriMo 5: The Lucas-Lehmer Test

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

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 $s_0 = 4$ .
For each $k > 0$ , define $s_k = (s_{k-1}^2 - 2) \bmod {M_n}$ .
Then $M_n$ is prime if and only if $s_{n-2} = 0$ .

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

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

For $M_7 = 127$ , we get

$\begin{array}{c|cccccc} k & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline s_k & 4 & 14 & 67 & 42 & 111 & 0 \end{array}$

so $M_7$ is prime. For $M_{11} = 2047$ , we get

$\begin{array}{c|cccccccccc} k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline s_k & 4 & 14 & 194 & 788 & 701 & 119 & 1877 & 240 & 282 & 1736 \end{array}$

so $M_{11}$ 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.

View all posts by Brent →

3 Responses to MaBloWriMo 5: The Lucas-Lehmer Test

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

November 8, 2015 at 2:33 am

The first sentence should have $M_n = 2^n – 1$ I believe. Anyway, this series of blog posts seems really nice. Thanks for that!
- Brent says:
  
  November 9, 2015 at 1:14 pm
  
  Thanks, fixed!

Comments are closed.