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

25220Re: Fermat+Euler+Frobenius

Expand Messages
  • paulunderwooduk
    Jul 18, 2013
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
      >
      >
      >
      > --- In primenumbers@yahoogroups.com,
      > "paulunderwooduk" <paulunderwood@> wrote:
      >
      > > Are the Gremlins now trapped?
      >
      > Decidedly not trapped. They now give you wriggle room,
      > where you may invent all sorts of post-hoc evasions.
      > Here is a counterexample to all your previous wriggles:
      >
      > {wriggle(a,n)=local(v=[a,3*a^2-1,5*a^2-1,13*a^2-1,3*a^2-7]);
      > sum(k=1,#v,gcd(v[k],n)>1)==0;}
      >
      > {tst(n,a)=kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
      > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
      > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
      > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
      > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
      >
      > {n=65886964889495717178571390281373531645585969659081927305601\
      > 05227985819505433064526820837352190304323548383200875256409729;
      >
      > a=28531673532383337956613397336948328674189469877146000735221\
      > 4200436155528207860632250156996971542498419889463170302428920;
      >
      > if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}
      >
      > Gremlins are still happy
      >
      > My comment: Gremlins are still being very generous; an
      > additional post-hoc wriggle, on your part, should not be
      > hard to find. Yet beware: Gremlins are cunning and if you
      > wriggle out of this counterexample, by invoking yet another
      > post-hoc gcd, they will quickly retaliate.
      >

      Thanks again, but rules were not followed; The wriggle is slightly wrong, but the counterexample is good for the Gremlins. It should be:

      {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
      sum(k=1,#v,gcd(v[k],n)>1)==0;}

      The main test should have the Euler+Lucas instead of Frobenius, but I made an error in previous code. Thanks for correcting that. Now I notice that for the most recent counterexample:
      Mod((3*a^2+1),n)^((n-1)/2) is neither 1 nor -1
      and (equally?)
      Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/(3*a^2+1),n))*L+1)^((n+1)/2) is neither 1 nor -1

      Paul
    • Show all 24 messages in this topic