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 ?

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.