# Lucas-Lehmer test for Mersenne and Wagstaff numbers?

Here is what I observed :

Let $$M_p = 2^p-1$$ for Mersenne numbers and $$W_p = (2^p+1)/3$$ for Wagstaff numbers with $$p$$ a prime number > $$2$$

Let the sequence $$S_i = 6 \cdot S_{i-1}^2 + 18 \cdot S_{i-1} +12$$ with $$S_0 = 12$$

Then $$M_p$$ or $$W_p$$ is prime if $$S_{p-2} \equiv 0 \pmod{M_p}$$ or $$S_{p-2} \equiv 0 \pmod{W_p}$$

For example let's take $$17$$ for both case with PARI GP :

For $$M_{17}$$ we get :

Mod(12, 131071)
Mod(1092, 131071)
Mod(96618, 131071)
Mod(85540, 131071)
Mod(22888, 131071)
Mod(99467, 131071)
Mod(4058, 131071)
Mod(49706, 131071)
Mod(96810, 131071)
Mod(97352, 131071)
Mod(21854, 131071)
Mod(109865, 131071)
Mod(81598, 131071)
Mod(36387, 131071)
Mod(131069, 131071)
Mod(0, 131071)


$$S_{p-2} \equiv 0 \pmod{M_{17}}$$ so $$131071$$ is prime.

For $$W_{17}$$ we get :

Mod(12, 43691)
Mod(1092, 43691)
Mod(9128, 43691)
Mod(43125, 43691)
Mod(33247, 43691)
Mod(2111, 43691)
Mod(37044, 43691)
Mod(33796, 43691)
Mod(37321, 43691)
Mod(31573, 43691)
Mod(3181, 43691)
Mod(39346, 43691)
Mod(36262, 43691)
Mod(3520, 43691)
Mod(43690, 43691)
Mod(0, 43691)


$$S_{p-2} \equiv 0 \pmod{W_{17}}$$ so $$43691$$ is prime.

It's better to use the original sequence $$S^2-2$$ for Mersenne numbers, but with the new sequence, it seems it works for both $$M_p$$ and $$W_p$$ for primality testing

Is there a way to prove this ?

I noticed than the sequence can be written as $$6(S+1)(S+2)$$ and when the starting value is $$12$$, $$S = 1/6 \cdot (3^{(2^{(2 + n)})}-9)$$ and interestingly the sum of the coefficients of the sequence is equal to the discriminant $$36 = 6^2$$.

• I am not an expert on the Lucas-Lehmer test(s), but it is probably worth noting that $$17 = 2^{2^2} + 1$$ is a Fermat prime. May 8 at 21:05

If you look at the sequence in OEIS A029858 changing the index is equal to the sequence you used then you get

$$S_{p-2}=\frac{3^{2^p-1}-3}{2}$$

for Mersenne numbers

but also

$$S_{p-2}=\frac{3^{2^p-1}-3}{2}=\frac{3^{2^p+1}-27}{18}=\frac{27 ^{\frac{2^p+1}{3}}-27}{18}$$

for Wagstaff numbers

and if you apply Fermat's little theorem you get the result you observed.