## 25220Re: Fermat+Euler+Frobenius

Expand Messages
• Jul 18, 2013
• 0 Attachment
>
>
>
> "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
> 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