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

Wagstaff question

Expand Messages
  • paulunderwooduk
    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
    • 0 Attachment
      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
    • 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 2 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 3 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.