mersenneforum.org n=x^3-x-1
 Register FAQ Search Today's Posts Mark Forums Read

 2021-01-18, 12:54 #1 paulunderwood     Sep 2002 Database er0rr E5C16 Posts n=x^3-x-1 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 (?) Last fiddled with by paulunderwood on 2021-01-18 at 13:01
 2021-01-24, 16:14 #2 alpertron     Aug 2002 Buenos Aires, Argentina 22·3·113 Posts 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: Code: 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.
2021-01-24, 22:34   #3
paulunderwood

Sep 2002
Database er0rr

22×919 Posts

Quote:
 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: Code: 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,