## 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!).

Assistant 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.

### 3 Responses to MaBloWriMo 5: The Lucas-Lehmer Test

1. janhrcek says:

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:

Thanks, fixed!