Quote:
Originally Posted by paulunderwood
Here are tests for Wagstaff (2^p+1)/3:
If p==1 mod 6:
Code:
w1(p)=s=Mod(4,(2^p+1)/3);for(k=1,p2,s=s^22);s==4
If p==5 mod 6:
Code:
w5(p)=s=Mod(4,(2^p+1)/3);for(k=1,p1,s=s^22);s==4
Can you prove or disprove either of these?

let p > 3 be a prime number, M = (2^p + 1)/3. Then M == 3 (mod 8).
Let u = Mod(x, x^2  4*x + 1), so that u^2  4*u + 1 = 0.
Let R = Z[u] = ring of algebraic integers in Q(sqrt(3)).
If p == 5 (mod 6), then M == 2 (mod 3). If M is prime, then (3/M) = +1, so MR = PP', R/P and R/P' both isomorphic to Z/MZ. Thus
u^(M1) == 1 (mod MR).
If v = u  1, we have norm(v) = 2, so that
v^(M1) == 1 (mod MR) also. Now
v^2 = 2*u, so that
v^(M1) = 2^((M1)/2) * u^((M1)/2). Thus
2^((M1)/2) * u^((M1)/2) == 1 (mod MR). Now (2/M) = 1, so we have
u^((M1)/2) == 1 (mod MR). Cubing, we obtain
u^(2^(p1)  1) == 1 (mod MR), or
u^(2^(p1)) == u (mod MR),
which validates Paul's test as a necessary condition that (2^p + 1)/3 be prime, when p == 5 (mod 6).

If p == 1 (mod 6), then M == 1 (mod 3). If M is prime, then (3/M) = 1, so MR is a prime ideal, and R/MR = GF(M^2). In this case, the Frobenius automorphism gives us that, for any r in R, if r' is the algebraic conjugate of r,
r^M == r' (mod MR), so that
r^(M+1) == r*r' = norm(r) (mod M). In particular,
u^(M+1) == 1 (mod MR) and
v^(M+1) == 2 (mod MR). Proceeding as above, we obtain
2 == 2^((M+1)/2) * u^((M+1)/2).
Now 2^((M+1)/2) = 2*(2^((M1)/2) == 2 (mod M), since (2/M) = 1. Therefore
u^((M+1)/2) == +1 (mod MR). This tells us that
u^((M+1)/4) == +1 or 1 (mod MR). If +1 is correct, we obtain
u^(2^(p2)) == u^(1) (mod MR), which would validate Paul's test as a necessary condition that (2^p + 1)/3 be prime, when p == 1 (mod 6).
Alas, I have so far been unable to determine in general whether it is +1 or 1.
I note that in this case, M == 19 (mod 24). I looked at
u^((q+1)/4) (mod qR) for q prime, q == 19 (mod 24)
and found that
u^((q+1)/4) == +1 (mod qR) about half the time, and
u^((q+1)/4) == 1 (mod qR) about half the time.
The smallest q == 19 (mod 24) for which
u^((q+1)/4) == 1 (mod qR)
is q = 67.
And that's as far as I've gotten.