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

Advertisements

About Brent

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. Pingback: MaBloWriMo 6: The Proof Begins | The Math Less Traveled

  2. 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!

Comments are closed.