## 25203Fermat+Euler+Fobenius

Expand Messages
• Jul 15 6:54 AM
Hi.

Let M=[x,-1;1,0], which is the companion matrix of L^2-x*L+1.

The characteristic equations of M+Id*a and M-Id*a, where Id is the 2x2 identity matrix, are:
L^2-(x+2*a)*L+1+a^2+a*x==0
L^2-(x-2*a)*L+1+a^2-a*x==0

Let x=2*a.

Then the characteristic equations become:
L^2-4*a*L+3*a^2+1==0
L^2-(a^2-1)==0

Let D=x^2-4==4*(a^2-1).

Define the composite test for odd, non-square n, coprime to 3 and any suitable a:
kronecker(a^2-1,n)==-1
gcd(a,n)==1

and do sub-tests:
(a^2-1)^((n-1)/2)==-1 (mod n)
(a^2-9)^(n-1)==1 (mod n)
(L+a)^(n+1)==3*a^2+1 (mod n, L^2-2*a*L+1)

In pari-speak:
{tst(n,a)=kronecker(a^2-1,n)==-1&&
gcd(a,n)==1&&
Mod(a^2-1,n)^((n-1)/2)==-1&&
Mod(a^2-9,n)^(n-1)==1&&
Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}

I have currently searched Richard Pinch's list of Carmichael Numbers where n<=241242001 and for all n<1870001 (both with all possible a) without counterexamples to this composite test. However, since this test has only one Lucas Sequence component, I expect the Gremlins to be able to find a counterexample :-)

I am running a hack of David's script:

{tst(n,x)=kronecker((x)^2-1,n)==-1&&gcd(x,n)==1&&
Mod(x^2-9,n)^(n-1)==1&&
Mod(x^2-1,n)^((n-1)/2)==-1&&
Mod(Mod(1,n)*(L+x),L^2-(2*x)*L+1)^(n+1)==3*x^2+1;}

{tst1(p,q)=local(n=p*q,u=[]);
for(a=3,p-3,if((n%(p-1)==1||(Mod(a^2-9,p)^(n-1)==1&&
Mod(a^2-1,p)^(n-1)==1))&&
Mod(Mod(1,p)*(L+a),L^2-(2*a)*L+1)^(n+1)==3*a^2+1,
u=concat(u,a)));Mod(u,p);}

{tst2(p,q)=local(n=p*q,up,uq,a,V=[]);
up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq,
for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
if(tst(n,a),V=concat(V,a))))));V=vecsort(V);
if(#V,print([n,V[1]]));V;}

{forprime(p=7,40000,for(k=4,12,q=1+2*k*(p-1);
if(ispseudoprime(q),tst2(p,q))));
print("\\\\ "round(gettime/1000)" seconds");}

Is it sane?

I have also checked under* from http://physics.open.ac.uk/~dbroadhu/cert/ with another hack of one of David's scripts:

{tst(n,x)=kronecker(x^2-1,n)==-1&&
gcd(x,n)==1&&
Mod(x^2-1,n)^((n-1)/2)==-1&&
Mod(x^2-9,n)^(n-1)==1&&
Mod(Mod(1,n)*(L+x),L^2-2*x*L+1)^(n+1)==3*x^2+1));}

for(k=1,#v,n=v[k][1];x=v[k][2];
if(tst(n,x)&&!isprime(n),c++));
print(c"/"#v" counterexamples left in "file);c;}

{tstfile("underbh4.txt");}
{tstfile("underbh6.txt");}
{tstfile("underw97.txt");}
{tstfile("underw297.txt");}
{tstfile("underw65.txt");}
{tstfile("underw65x.txt");}
{tstfile("underwg.txt");}
{tstfile("underwqd.txt");}

Paul
• Show all 24 messages in this topic