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

25203Fermat+Euler+Fobenius

Expand Messages
  • paulunderwooduk
    Jul 15 6:54 AM
      Hi.

      Let M=[x,-1;1,0], which is the companion matrix of L^2-x*L+1.

      The characteristic equations of M+Id*a and M-Id*a, where Id is the 2x2 identity matrix, are:
      L^2-(x+2*a)*L+1+a^2+a*x==0
      L^2-(x-2*a)*L+1+a^2-a*x==0

      Let x=2*a.

      Then the characteristic equations become:
      L^2-4*a*L+3*a^2+1==0
      L^2-(a^2-1)==0

      Let D=x^2-4==4*(a^2-1).

      Define the composite test for odd, non-square n, coprime to 3 and any suitable a:
      kronecker(a^2-1,n)==-1
      gcd(a,n)==1

      and do sub-tests:
      (a^2-1)^((n-1)/2)==-1 (mod n)
      (a^2-9)^(n-1)==1 (mod n)
      (L+a)^(n+1)==3*a^2+1 (mod n, L^2-2*a*L+1)

      In pari-speak:
      {tst(n,a)=kronecker(a^2-1,n)==-1&&
      gcd(a,n)==1&&
      Mod(a^2-1,n)^((n-1)/2)==-1&&
      Mod(a^2-9,n)^(n-1)==1&&
      Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}

      I have currently searched Richard Pinch's list of Carmichael Numbers where n<=241242001 and for all n<1870001 (both with all possible a) without counterexamples to this composite test. However, since this test has only one Lucas Sequence component, I expect the Gremlins to be able to find a counterexample :-)

      I am running a hack of David's script:

      {tst(n,x)=kronecker((x)^2-1,n)==-1&&gcd(x,n)==1&&
      Mod(x^2-9,n)^(n-1)==1&&
      Mod(x^2-1,n)^((n-1)/2)==-1&&
      Mod(Mod(1,n)*(L+x),L^2-(2*x)*L+1)^(n+1)==3*x^2+1;}

      {tst1(p,q)=local(n=p*q,u=[]);
      for(a=3,p-3,if((n%(p-1)==1||(Mod(a^2-9,p)^(n-1)==1&&
      Mod(a^2-1,p)^(n-1)==1))&&
      Mod(Mod(1,p)*(L+a),L^2-(2*a)*L+1)^(n+1)==3*a^2+1,
      u=concat(u,a)));Mod(u,p);}

      {tst2(p,q)=local(n=p*q,up,uq,a,V=[]);
      up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq,
      for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
      if(tst(n,a),V=concat(V,a))))));V=vecsort(V);
      if(#V,print([n,V[1]]));V;}

      {forprime(p=7,40000,for(k=4,12,q=1+2*k*(p-1);
      if(ispseudoprime(q),tst2(p,q))));
      print("\\\\ "round(gettime/1000)" seconds");}

      Is it sane?

      I have also checked under* from http://physics.open.ac.uk/~dbroadhu/cert/ with another hack of one of David's scripts:

      {tst(n,x)=kronecker(x^2-1,n)==-1&&
      gcd(x,n)==1&&
      Mod(x^2-1,n)^((n-1)/2)==-1&&
      Mod(x^2-9,n)^(n-1)==1&&
      Mod(Mod(1,n)*(L+x),L^2-2*x*L+1)^(n+1)==3*x^2+1));}

      {tstfile(file)=local(c,n,x,v=readvec(file));
      for(k=1,#v,n=v[k][1];x=v[k][2];
      if(tst(n,x)&&!isprime(n),c++));
      print(c"/"#v" counterexamples left in "file);c;}

      {tstfile("underbh4.txt");}
      {tstfile("underbh6.txt");}
      {tstfile("underw97.txt");}
      {tstfile("underw297.txt");}
      {tstfile("underw65.txt");}
      {tstfile("underw65x.txt");}
      {tstfile("underwg.txt");}
      {tstfile("underwqd.txt");}

      Paul
    • Show all 24 messages in this topic