n=x^3-x-1

[paulunderwood]

Let n=x^3-x-1 for x integer >2. In the past I have tested x^n==x mod n => n is prime.

Let's start with n=p*q. Note that either p or q is congruent to -1 mod 4 and either p or q is congruent to -1 mod 6.

Assume the case p=4*a-1. Then x^(4*a-2)==1 mod p. Now assume q=3*(4*a-2)+1. Then x^(12*a-5)==x mod q. So x^((4*a-1)*(12*a-5))==x mod n. Or x^(48*a^2-32*a+5)==x mod n. This is impossible since n is -1 mod 4.

Next assume p==6*a-1 and q=2*(6*a-2)+1. Then x^(12*a-3)==x mod q. But the exponent is divisble by 3.

Assume p=4*a+1 and q=8*a-1. Then x^((8*a-2)*4*a+1)==x mod n which is impossible since the exponent is 1 mod 4. The same argument for any q=k*(4*a)-1.

If k>3 and q=k*(p-1)+1 then x^(p*q) == x mod n implies x^p == x mod q or x^(p-1)==1 mod q but this has p-1 roots mod q and x^3-x-1 has only 3 roots, whilst x^(q-1)=1 has at least 4 times as many.

Things get more complicated with n having more than 2 factors. Here is a numerical example. n=11*31*61*151 then x^(11*31*151) == x mod 61 or x^11==x mod 61 or x^10==1 mod 61 an impossibility in the difference between the number of roots.

To be continued (?)

[alpertron]

I've just tested the first sentence written by the OP with values of x up to 10 million using the following line in PARI-GP:

for (x=2,10000000,n=x^3-x-1;if (Mod(x,n)^n==Mod(x,n) && isprime(n)==0,print(x)))

After a few minutes, the execution finished with no values of x printed, so it holds up to that bound.

[paulunderwood]

Originally Posted by alpertron

I've just tested the first sentence written by the OP with values of x up to 10 million using the following line in PARI-GP:

for (x=2,10000000,n=x^3-x-1;if (Mod(x,n)^n==Mod(x,n) && isprime(n)==0,print(x)))

After a few minutes, the execution finished with no values of x printed, so it holds up to that bound.

Back in 2003, we tested with at least 5 miller-rabin rounds for x<223,490,000,000. Still no proof forthcoming.

A lot of what I wrote in the OP was complete rubbish,