mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-01-18, 12:54   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·733 Posts
Lightbulb 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
paulunderwood is offline   Reply With Quote
Old 2021-01-24, 16:14   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·3·113 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2021-01-24, 22:34   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110010100012 Posts
Default

Quote:
Originally Posted by alpertron View Post
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,
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 10:39.

Sun May 9 10:39:39 UTC 2021 up 31 days, 5:20, 0 users, load averages: 2.29, 2.84, 3.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.