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