20220313, 13:39  #1 
Sep 2002
Database er0rr
29×151 Posts 
mod x^4+1
You may be aware that no one has found a counterexample to the test Mod(Mod(x+2,n),x^2+1)^(n+1)==5 for n%4==3.
I propose the test Mod(Mod(x+1,n),x^4+1)^(n1) for odd n with the following results
Last fiddled with by paulunderwood on 20220313 at 13:43 
20220313, 18:51  #2  
Feb 2017
Nowhere
6,101 Posts 
Quote:
So there are no counterexamples to these with n prime I have no idea how to try to construct composite n congruent to 3, 5, or 7 (mod 8) for which these congruences hold. EDIT: BTW, the test for numbers congruent to 1 (mod 4) corresponding to the test you gave for numbers congruent to 3 (mod 4) is lift(lift(Mod(Mod(1,n)*x + 2,x^2 + 1)^(n1))) == 1. Every prime congruent to 1 (mod 4) other than 5 satisfies this condition. (Why 5 is exceptional is left as an exercise for the reader.) But the condition is rife with pseudoprimes, as the following mindless sweep shows: Code:
? forstep(n=5,100000,4,r=lift(lift(Mod(Mod(1,n)*x+2,x^2+1)^(n1)));if(r==1&&!ispseudoprime(n),print(n" "factor(n)))) 15841 [7, 1; 31, 1; 73, 1] 29341 [13, 1; 37, 1; 61, 1] 38081 [113, 1; 337, 1] 40501 [101, 1; 401, 1] 41041 [7, 1; 11, 1; 13, 1; 41, 1] 46657 [13, 1; 37, 1; 97, 1] 75361 [11, 1; 13, 1; 17, 1; 31, 1] Code:
? forstep(n=9,500000,8,r=lift(lift(Mod(Mod(1,n)*x+1,x^4+1)^(n1)));if(r==1&&!ispseudoprime(n),print(n" "factor(n)))) 15841 [7, 1; 31, 1; 73, 1] 162401 [17, 1; 41, 1; 233, 1] 410041 [41, 1; 73, 1; 137, 1] Last fiddled with by Dr Sardonicus on 20220314 at 01:05 

20220314, 04:47  #3 
Sep 2002
Database er0rr
29×151 Posts 
The test over x^2+1 can be computed with 2 Selfridges. Over x^4+1 it is 8 Selfridges by combining the difference of squares:
Code:
? Mod(s*x^3+t*x^2+u*x+v,x^4+1)^2 Mod((2*v*s + 2*u*t)*x^3 + (s^2 + (2*v*t + u^2))*x^2 + (2*t*s + 2*v*u)*x + (2*u*s + (t^2 + v^2)), x^4 + 1) ? Mod(s*x^3+t*x^2+u*x+v,x^4+1)*(x+1) Mod((s + t)*x^3 + (t + u)*x^2 + (u + v)*x + (s + v), x^4 + 1) 
20220314, 12:36  #4 
Feb 2017
Nowhere
6,101 Posts 

20220314, 13:17  #5  
Sep 2002
Database er0rr
29·151 Posts 
Quote:
The others I tend to test up to 10^8  takes a minute or two. Furthermore, for n%4==3 I can test base x+2 over x^2+1, for n%8==5 base x+1 over x^4+1, for n%16==9 base x+1 over x^8+1 and so on, with the number of Selfridges ballooning. Last fiddled with by paulunderwood on 20220314 at 13:25 

20220315, 14:22  #6  
Feb 2017
Nowhere
6,101 Posts 
Hmm. Might be time to start thinking about how to construct composite n that "fool" the test.
Quote:
Quote:
lift(lift(Mod(Mod(1,n)*x,x^2  a*x + 1)^(n+1)))==1 with avalues such that kronecker(a^2  4, n) == 1 could you run for the same number of Selfridges? (I'm assuming the computational cost of determining such avalues is negligible in comparison. I am also disregarding any pertinent gcd(poly in a, n) conditions which I assume are likewise computationally very cheap.) 

20220315, 14:51  #7  
Sep 2002
Database er0rr
29×151 Posts 
Quote:
Last fiddled with by paulunderwood on 20220315 at 14:52 

20220315, 15:05  #8 
Sep 2002
Database er0rr
10433_{8} Posts 
Considering n%8==5 with Mod(Mod(x+1,n),x^4+1)^n==1x as the main test, can you find any k such that Mod(Mod(x+1,n),x^4+1)^k==1x for composite n?
Last fiddled with by paulunderwood on 20220315 at 15:07 
20220315, 15:16  #9  
Feb 2017
Nowhere
6,101 Posts 
Quote:
Evidently, none up to 10^8 since you've tested that far. I don't intend to do a numerical sweep above that point, so if you want more searching above 10^8, you'll have to do it yourself or get someone else to do it. I have been thinking about ways to construct pseudoprimes  but no good ideas yet. 

20220315, 15:23  #10  
Sep 2002
Database er0rr
29×151 Posts 
Quote:
Last fiddled with by paulunderwood on 20220315 at 15:26 

20220315, 23:29  #11 
Sep 2002
Database er0rr
29×151 Posts 
n%8==5 tested up to n<10^10. I will take it to the next exponent.
Last fiddled with by paulunderwood on 20220315 at 23:29 