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

Re: 1+1+1+2 selfridge composite test and a question

Expand Messages
  • paulunderwooduk
    The characteristic equation of [x+2,-2;2,-x+2] is L^2-4*L-x^2+8==0 Let P=4 Q=-(x^2-8) ... The gremlins score another goal with their counterexample:
    Message 1 of 14 , Oct 4, 2012
      The characteristic equation of [x+2,-2;2,-x+2]
      is L^2-4*L-x^2+8==0

      Let
      P=4
      Q=-(x^2-8)

      > Then
      > v=P^2/Q-2 == -2*x^2/(x^2-8)
      >
      > For this new test of odd n, find x such that:
      > gcd(x,n)==1
      > gcd(x^2-8,n)==1
      > kronecker(x^2-4)==-1
      >
      > and perform the sub-tests:
      > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
      > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
      > x^(n-1)==1 (mod n)
      > L^(n+1)==1 (mod n, L^2-v*L+1)
      >
      > I am testing all x against psp-2 n below 2^32.
      >

      The gremlins score another goal with their counterexample:
      n==741470549 and x==68216238.

      I refuse to take their bait of x^((n-1)/2)!=+-1 (mod n) and "recant"

      Paul
    • paulunderwooduk
      ... I noticed: x^((n-1)/2)==593203119 (mod n) L^((n+1)/2)==593203119 (mod n) This got me thinking again... kronecker(v^2-4,n)
      Message 2 of 14 , Oct 4, 2012
        >
        > The characteristic equation of [x+2,-2;2,-x+2]
        > is L^2-4*L-x^2+8==0
        >
        > Let
        > P=4
        > Q=-(x^2-8)
        >
        > > Then
        > > v=P^2/Q-2 == -2*x^2/(x^2-8)
        > >
        > > For this new test of odd n, find x such that:
        > > gcd(x,n)==1
        > > gcd(x^2-8,n)==1
        > > kronecker(x^2-4)==-1
        > >
        > > and perform the sub-tests:
        > > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
        > > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
        > > x^(n-1)==1 (mod n)
        > > L^(n+1)==1 (mod n, L^2-v*L+1)
        > >
        > > I am testing all x against psp-2 n below 2^32.
        > >
        >
        > The gremlins score another goal with their counterexample:
        > n==741470549 and x==68216238.
        >

        I noticed:
        x^((n-1)/2)==593203119 (mod n)
        L^((n+1)/2)==593203119 (mod n)

        This got me thinking again...

        kronecker(v^2-4,n)
        ==kronecker((4*x^4-4*(-x^2+8)^2)/(-x^2+8)^2,n)
        ==kronecker(4*x^4-4*(x^4-16*(x^2-4)),n)
        ==kronecker(x^2-4,n)
        ==-1

        Hence L^((n+1)/2)==kronecker(v+2,n) (mod n, L^2-v*L+1)

        kronecker(v+2,n)
        ==kronecker(P^2/Q,n)
        ==kronecker(Q,n)

        Thus the Lucas test now becomes
        L^((n+1)/2)==kronecker(-x^2+8,n)

        I will continue testing psp-2s :-)

        Paul
      • paulunderwooduk
        Hi, for odd n with minimal x such that kronecker(x^2-4,n)==-1, if x=0 then 2 selfridge: (L+2)^(n+1)==5 (mod n, L^2+1) if x=1 then 3 selfridge: gcd(7,n)==1
        Message 3 of 14 , Oct 8, 2012
          Hi,

          for odd n with minimal x such that kronecker(x^2-4,n)==-1,

          if x=0 then 2 selfridge:
          (L+2)^(n+1)==5 (mod n, L^2+1)

          if x=1 then 3 selfridge:
          gcd(7,n)==1
          3^((n-1)/2)==kronecker(3,n) (mod n)
          L^((n+1)/2)==kronecker(3,n) (mod n, L^2-(2/7)*L+1)

          if x=3 then 4 selfridge:
          gcd(3,n)==1
          3^(n-1)==1 (mod n)
          5^((n-1)/2)==-1 (mod n)
          L^((n+1)/2)==kronecker(-1,n) (mod n, L^2+18*L+1)

          if n>x>3 then 4 selfridge:
          (L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
          (L-2)^(n+1)==5-2*x (mod n, L^2-x*L+1)

          This program is on average (1/2)*2+(1/2)*((1/2)*3+(1/2)*((1/2)*4+(1/2)*4)==2.75 selfridges.

          It is a mix of "section 10" of my paper in the file section of this group:
          http://tech.groups.yahoo.com/group/primenumbers/files/Articles/
          and of http://tech.groups.yahoo.com/group/primenumbers/message/24525

          Paul
        • paulunderwooduk
          ... This should be L^((n+1)/2)==kronecker(7,n) (mod n, L^2-(2/7)*L+1)
          Message 4 of 14 , Oct 9, 2012
            I need to report an of error:

            > for odd n with minimal x such that kronecker(x^2-4,n)==-1,
            >
            > if x=0 then 2 selfridge:
            > (L+2)^(n+1)==5 (mod n, L^2+1)
            >
            > if x=1 then 3 selfridge:
            > gcd(7,n)==1
            > 3^((n-1)/2)==kronecker(3,n) (mod n)
            > L^((n+1)/2)==kronecker(3,n) (mod n, L^2-(2/7)*L+1)

            This should be L^((n+1)/2)==kronecker(7,n) (mod n, L^2-(2/7)*L+1)

            >
            > if x=3 then 4 selfridge:
            > gcd(3,n)==1
            > 3^(n-1)==1 (mod n)
            > 5^((n-1)/2)==-1 (mod n)
            > L^((n+1)/2)==kronecker(-1,n) (mod n, L^2+18*L+1)
            >
            > if n>x>3 then 4 selfridge:
            > (L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
            > (L-2)^(n+1)==5-2*x (mod n, L^2-x*L+1)
            >
            > This program is on average (1/2)*2+(1/2)*((1/2)*3+(1/2)*((1/2)*4+(1/2)*4)==2.75 selfridges.
            >
            > It is a mix of "section 10" of my paper in the file section of this group:
            > http://tech.groups.yahoo.com/group/primenumbers/files/Articles/
            > and of http://tech.groups.yahoo.com/group/primenumbers/message/24525
            >
            > Paul
            >
          • paulunderwooduk
            I have changed the rules and added a puzzle. For odd n with x chosen in order from {0,1,6,3,all others} so that kronecker(x^2-4,n)==-1, ... if x=6 then 4
            Message 5 of 14 , Oct 9, 2012
              I have changed the rules and added a puzzle.

              For odd n with x chosen in order from {0,1,6,3,all others} so that kronecker(x^2-4,n)==-1,

              > > if x=0 then 2 selfridge:
              > > (L+2)^(n+1)==5 (mod n, L^2+1)
              > >
              > > if x=1 then 3 selfridge:
              > > gcd(7,n)==1
              > > 3^((n-1)/2)==kronecker(3,n) (mod n)
              > L^((n+1)/2)==kronecker(7,n) (mod n, L^2-(2/7)*L+1)

              if x=6 then 4 selfridge:
              gcd(21,n)==1
              6^(n-1)==1 (mod n) (*)
              2^((n-1)/2)==kronecker(2,n) (mod n)
              L^((n+1)/2)==kronecker(-7,n) (mod n, L^2+(18/7)*L+1)

              > >
              > > if x=3 then 4 selfridge:
              > > gcd(3,n)==1
              > > 3^(n-1)==1 (mod n)
              > > 5^((n-1)/2)==-1 (mod n)
              > > L^((n+1)/2)==kronecker(-1,n) (mod n, L^2+18*L+1)
              > >
              > > if n>x>3 then 4 selfridge:
              > > (L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
              > > (L-2)^(n+1)==5-2*x (mod n, L^2-x*L+1)
              > >
              > > This program is on average (1/2)*2+(1/2)*((1/2)*3+(1/2)*((1/2)*4+(1/2)*4)==2.75 selfridges.
              > >

              Puzzle: find a counterexample for x==6 where (*) is dropped,

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