# Lucas-Lehmer test for Wagstaff numbers?

Here is what I observed :

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

Let the sequence $$S_i = S_{i-1}^2 - 2$$ with $$S_0 = (2^{p-2}+1)/3$$.

Then $$W_p$$ is prime if $$S_{p-2} \equiv 10 \cdot S_0 - 1 (mod N_p)$$ and $$p \equiv 2 (mod 3)$$ or $$S_{p-2} \equiv 2 \cdot S_0 + 1 (mod N_p)$$ and $$p \equiv 1 (mod 3)$$

for example with $$p = 17$$ we get this on PARI/GP :

Mod(10923, 131073)
Mod(35497, 131073)
Mod(32258, 131073)
Mod(121088, 131073)
Mod(84743, 131073)
Mod(17450, 131073)
Mod(19919, 131073)
Mod(8588, 131073)
Mod(90716, 131073)
Mod(105422, 131073)
Mod(118412, 131073)
Mod(129713, 131073)
Mod(14576, 131073)
Mod(121514, 131073)
Mod(16598, 131073)
Mod(109229, 131073)


$$17 \equiv 2 (mod 3)$$ and we get $$10 \cdot (2^{17-2}+1)/3 - 1$$ at the last residue and $$(2^{17}+1)/3 = 43691$$ and this is indeed prime.

You can run the test here.

And if it's true for all prime, is there a way to proving this ?

• a more efficient primality test for $W_p$ could be to check if $25^{2^{p-1}}=25$ modulo $N_p$. Jan 2 at 11:05

Yes, if $$W_p$$ is prime, this congruence holds, and the proof is less or more standard (similar to that of necessity in the Lucas--Lehmer test).
At first, the congruence holds modulo $$3$$, since all $$S_i$$'s for $$i\geqslant 1$$ are congruent to 2 modulo 3, and $$S_0\equiv 0\pmod 3$$ for $$p=3k+2$$, $$S_0\equiv 2\pmod 3$$ for $$p=3k+1$$. Thus, it remains to prove the congruence modulo $$W_p$$. It reads as $$S_{p-2}\equiv 3/2 \pmod{W_p}$$ in both cases.
It is easy to see that $$W_p\equiv 3\pmod 4$$ and $$W_p\in \{1,4\} \pmod 7$$ that yields $$(\frac{-7}{W_p})=(\frac{-1}{W_p})(\frac{7}{W_p})= -(\frac{7}{W_p})=(\frac{W_p}{7})=1$$, and we may consider an element $$\alpha:=(1+3\sqrt{-7})/8\in \mathbb{F}_{W_p}$$ (we fix a value of $$\sqrt{-7}$$ arbitrarily). We have $$\alpha^{-1}=(1-3\sqrt{-7})/8$$, so $$\alpha+\alpha^{-1}=1/4=S_0$$. Therefore $$S_i=\alpha^{2^i}+\alpha^{-2^i}$$ by induction. Note that $$\alpha=\beta^2$$ for $$\beta=(3+\sqrt{-7})/4$$, so $$S_{p-2}=3/2$$ reads as $$\beta^{2^{p-1}}+\beta^{-2^{p-1}}=3/2=\beta+\beta^{-1},$$ and it suffices to prove that $$\beta^{2^{p-1}}=\beta$$, or, equivalently, that $$\beta^{2^{p-1}-1}=1$$. Since $$2^{p-1}-1$$ is divisible by $$(W_p-1)/2=(2^{p-1}-1)/3$$, it is enough to prove that $$\beta$$ is a quadratic residue modulo $$W_p$$. We have $$(1-\sqrt{-7})^2=-6-2\sqrt{-7}=-2^3\cdot \beta$$, and $$\left(\frac{\beta}{W_p}\right)=\left(\frac{-2}{W_p}\right)=\left(\frac{-1}{W_p}\right)\left(\frac{2}{W_p}\right)=(-1)\cdot(-1)=1,$$ as $$W_p\equiv 3\pmod 8$$.