Loading ...
Sorry, an error occurred while loading the content.

Re: Wagstaff question

Expand Messages
  • djbroadhurst
    ... 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 1 of 3 , Jun 13, 2011
    • 0 Attachment
      --- 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.

      David
    • paulunderwooduk
      ... 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 2 of 3 , Jun 14, 2011
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
        >
        >
        >
        > --- 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.
        >

        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.