## 25224Re: Fermat+Euler+Frobenius

Expand Messages
• Jul 18, 2013
>
>
>
> "paulunderwooduk" <paulunderwood@> wrote:
>
> > > David, sorry for the noise. Here is what I have in mind:
> > Oh dear, I meant ...
> > Paul -- suffering from error-after-posting syndrome
>
> After tidying up your request, the Gremlims happily obliged:
>
> {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)=local(Q=3*a^2+1);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(Q,n)^((n-1)/2)==kronecker(Q,n)&&
> Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}
>
> {if(tst(9526822969*133375521553,244578343630781166947),
> print(" Gremlins rule OK"));}
>
> Gremlins rule OK
>

They do indeed rule. I now present a puzzle: make all the tests "strong" i.e. check roots of 1 where possible. Of course, if n==3 (mod 4) a strong Lucas test will be enough,

With thanks,

Paul
• Show all 24 messages in this topic