20210118, 12:54  #1 
Sep 2002
Database er0rr
2^{2}×1,063 Posts 
n=x^3x1
Let n=x^3x1 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*a1. Then x^(4*a2)==1 mod p. Now assume q=3*(4*a2)+1. Then x^(12*a5)==x mod q. So x^((4*a1)*(12*a5))==x mod n. Or x^(48*a^232*a+5)==x mod n. This is impossible since n is 1 mod 4. Next assume p==6*a1 and q=2*(6*a2)+1. Then x^(12*a3)==x mod q. But the exponent is divisble by 3. Assume p=4*a+1 and q=8*a1. Then x^((8*a2)*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*(p1)+1 then x^(p*q) == x mod n implies x^p == x mod q or x^(p1)==1 mod q but this has p1 roots mod q and x^3x1 has only 3 roots, whilst x^(q1)=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 20210118 at 13:01 
20210124, 16:14  #2 
Aug 2002
Buenos Aires, Argentina
5AE_{16} 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 PARIGP:
Code:
for (x=2,10000000,n=x^3x1;if (Mod(x,n)^n==Mod(x,n) && isprime(n)==0,print(x))) 
20210124, 22:34  #3  
Sep 2002
Database er0rr
2^{2}·1,063 Posts 
Quote:
A lot of what I wrote in the OP was complete rubbish, 
