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

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

Expand Messages
  • 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 1 of 14 , Oct 4, 2012
    View Source
    • 0 Attachment
      >
      > 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 2 of 14 , Oct 8, 2012
      View Source
      • 0 Attachment
        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 3 of 14 , Oct 9, 2012
        View Source
        • 0 Attachment
          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 4 of 14 , Oct 9, 2012
          View Source
          • 0 Attachment
            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.