## Wagstaff question

Expand Messages
• Hi, it seems from testing a few small values of N=(2^p+1)/3 that: if p == 1 (mod 6) then jacobi(0^2-4,N) == -1 and jacobi(4^2-4,N) == -1 if p == 5 (mod 6) then
Message 1 of 3 , Jun 13, 2011
Hi,

it seems from testing a few small values of N=(2^p+1)/3 that:

if p == 1 (mod 6) then jacobi(0^2-4,N) == -1 and jacobi(4^2-4,N) == -1
if p == 5 (mod 6) then jacobi(1^2-4,N) == -1 and jacobi(5^2-4,N) == -1

Is it true? Can someone give me an explanation?

Paul
• ... Your choice of letter p was unfortunate, since your proposition does not require p to be prime (whereas Wagstaff clearly did). So let s replace p by
Message 2 of 3 , Jun 13, 2011
"paulunderwooduk" <paulunderwood@...> wrote:

> it seems from testing a few small values of N=(2^p+1)/3 that:
> if p == 1 (mod 6) then jacobi(0^2-4,N) == -1 and jacobi(4^2-4,N) == -1
> if p == 5 (mod 6) then jacobi(1^2-4,N) == -1 and jacobi(5^2-4,N) == -1

Your choice of letter "p" was unfortunate, since your
proposition does not require p to be prime (whereas
Wagstaff clearly did). So let's replace "p" by "n":

{for(n=5,10^5,
if(n%6==1,N=(2^n+1)/3;
if(kronecker(-1,N)+1||kronecker(3,N)+1,print(p)));
if(n%6==5,N=(2^n+1)/3;
if(kronecker(-3,N)+1||kronecker(21,N)+1,print(p))));}

[no failures]

Note that I have demystified your kroneckers by extracting squares.

Now factorize kronecker(21,N) = kronecker(3,N)*kronecker(7,N).
The kroneckers with -1, -3 and 3 on the top are easy to predict.
The only non-trivial case seems to be with 7 on the top.
Here we invert the kronecker, to get kronecker(N,7), with a
sign flip, from Gaussian reciprocity. Finally, your discovery
boils down to an easily proved result.

Proposition: If n is coprime to 6, then (2^n+1)/3 is a square modulo 7.

Proof: If n = 1 mod 6, then (2^n+1)/3 = 1 mod 7 is the square of 1 mod 7.
If n = 5 mod 6, then (2^n+1)/3 = 4 mod 7 is the square of 2 mod 7.

Moral: Always try to demystify your kronecker symbols,
by intelligent factorization and inversion.

David
• ... Thank you, David, for a lucid explanation. I have a ulterior motive... Reinstating p prime, note that 2^p+1 == 0 (mod N) 2^p == -1 (mod N) 4^p == 1 (mod N)
Message 3 of 3 , Jun 14, 2011
>
>
>
> "paulunderwooduk" <paulunderwood@> wrote:
>
> > it seems from testing a few small values of N=(2^p+1)/3 that:
> > if p == 1 (mod 6) then jacobi(0^2-4,N) == -1 and jacobi(4^2-4,N) == -1
> > if p == 5 (mod 6) then jacobi(1^2-4,N) == -1 and jacobi(5^2-4,N) == -1
>
> Your choice of letter "p" was unfortunate, since your
> proposition does not require p to be prime (whereas
> Wagstaff clearly did). So let's replace "p" by "n":
>
> {for(n=5,10^5,
> if(n%6==1,N=(2^n+1)/3;
> if(kronecker(-1,N)+1||kronecker(3,N)+1,print(p)));
> if(n%6==5,N=(2^n+1)/3;
> if(kronecker(-3,N)+1||kronecker(21,N)+1,print(p))));}
>
> [no failures]
>
> Note that I have demystified your kroneckers by extracting squares.
>
> Now factorize kronecker(21,N) = kronecker(3,N)*kronecker(7,N).
> The kroneckers with -1, -3 and 3 on the top are easy to predict.
> The only non-trivial case seems to be with 7 on the top.
> Here we invert the kronecker, to get kronecker(N,7), with a
> sign flip, from Gaussian reciprocity. Finally, your discovery
> boils down to an easily proved result.
>
> Proposition: If n is coprime to 6, then (2^n+1)/3 is a square modulo 7.
>
> Proof: If n = 1 mod 6, then (2^n+1)/3 = 1 mod 7 is the square of 1 mod 7.
> If n = 5 mod 6, then (2^n+1)/3 = 4 mod 7 is the square of 2 mod 7.
>
> Moral: Always try to demystify your kronecker symbols,
> by intelligent factorization and inversion.
>

Thank you, David, for a lucid explanation.

I have a ulterior motive...

Reinstating p prime, note that

2^p+1 == 0 (mod N)
2^p == -1 (mod N)
4^p == 1 (mod N) (*)

Now consider the fermat test

4^N (mod N) == 4^((2^p+1)/3) (mod N) == 4^(2*m*p+1) (mod N)

for some integer m. Continuing

4^N (mod N) == 4*(4^p)^(2*m) (mod N) == 4*(1)^(2*m) (mod N)

by substituting (*). Hence 4^N == 4 (mod N) for all p.

Applying my {a-2,a+2} test (given in my Quadratic Composite Test available in the file section of this group -- to be updated later this year), Wagstaff numbers can be tested as follows:

If p == 1 (mod 6) then do the 2-selfridge test:
Mod(Mod(1,N)*l,l^2-4*l+1)^(N+1)==1

which conjecturally can be:
Mod(Mod(1,N)*l,l^2-4*l+1)^((N+1)/2)==1

If p == 5 (mod 6) then do the 3 -selfridge test:
Mod(5,n)^N==5
Mod(Mod(1,N)*l,l^2-5*l+1)^(N+1)==1

the latter part conjecturally can be:
Mod(Mod(1,N)*l,l^2-5*l+1)^((N+1)/2)==-1

I looked at M=(4^p+1)/5 and followed your logic to prove the conditions on a-2==6 and a+2==10, resulting in the 6-selfridge (PRP) test
Mod(6,M)^M==6
Mod(10,M)^M==10
Mod(Mod(1,M)*l,l^2-6*l+1)^(M+1)==1
Mod(Mod(1,M)*l,l^2-10*l+1)^(M+1)==1

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.