View Single Post
Old 2021-09-29, 17:18   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default

Code:
{tst(n,a)=gcd(a^3-a,n)==1&&kronecker(a^2-4,n)==-1&&Mod(Mod(x,n),x^2-a*x+1)^(n+1)==1;}

{tst1(n,a,t)=gcd(t^2-1,n)==1&&gcd(a+t,n)==1&&gcd(a*t+1,n)==1&&
Mod(t,n)^(n-1)==1&&Mod(Mod(x+t,n),x^2-a*x+1)^(n+1)==(a+t)*t+1;}

{tst2(n,a,t,t2)=gcd(t^2-t2^2,n)==1&&gcd((t*t2)^2-1,n)==1&&
tst(n,a)&&tst1(n,a,t)&&tst1(n,a,t2);}
This tst2 looks pretty sound. Can any one fool it?

It is based on A^n+t^n == (A+t)^n mod n and A^n+t2^n == (A+t2)^n mod n with the incumbent GCDs

Edit: I added in gcd(a^3-a,n)==1. Otherwise tst will be trivially degenerate into cyclotomy and the counterexample in post #7 would fool it!

Last fiddled with by paulunderwood on 2021-09-29 at 20:25
paulunderwood is offline   Reply With Quote