Lucas-Lehmer test for Wagstaff numbers?

Question

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 ?

Answer 1

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