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

25215Re: Fermat+Euler+Frobenius

Expand Messages
  • paulunderwooduk
    Jul 17, 2013
      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
      >
      >
      >
      > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
      >
      > > I notice Mod(a,n)^((n-1)/2) is neither 1 nor -1.
      >
      > Your latest wriggle is easily countered:
      >
      > {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&&
      > Mod(a,n)^((n-1)/2)==kronecker(a,n)&& \\ latest wriggle
      > 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=47391041614253942746775474638243609594331524373222569350310\
      > 52914770672055547658535429075770110985428014024530096070179809;
      >
      > a=23229351387100192392009446875150639001986809695144905977925\
      > 121834927356460863740859375485138643249550235752142747141519;
      >
      > if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}
      >
      > Gremlins are still happy
      >

      Thanks very much.

      Transforming the Frobenius PRP test into Euler+Lucas:

      Mod(3*a^2+1,n)^((n-1)/2)==kronecker(3*a^2+1,n)&&
      Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/(3*a^2+1),n))*L+1)^((n+1)/2)==kronecker(3*a^2+1,n)

      I notice that for your counterexample (and the one before it):
      gcd((13*a^2-1)*(7*a^2-3),n)>1,

      Are the Gremlins now trapped?

      Paul
    • Show all 24 messages in this topic