- --- In primenumbers@yahoogroups.com,

"paulunderwooduk" <paulunderwood@...> wrote:

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

Your choice of letter "p" was unfortunate, since your

> 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

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 - --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>

Thank you, David, for a lucid explanation.

>

>

> --- In primenumbers@yahoogroups.com,

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

>

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