20220316, 01:06  #12  
Feb 2017
Nowhere
2^{2}·5^{2}·61 Posts 
Quote:
No good ideas for this question, either. At least not yet. I'm pretty sure I know how to get closed formulas for the coefficients of (1+x)^k (mod x^4 + 1), but I'm not sure they'd help much with the question at hand. 

20220316, 05:45  #13 
Sep 2002
Database er0rr
29×151 Posts 
The companion matrix of x^4+1 is:
Code:
? cm=([0,0,0,1;1,0,0,0;0,1,0,0;0,0,1,0]) [0 0 0 1] [1 0 0 0] [0 1 0 0] [0 0 1 0] Code:
? cm+1 [1 0 0 1] [1 1 0 0] [0 1 1 0] [0 0 1 1] Code:
? matdet(cm+1) 2 Answer: Yes, according to https://en.wikipedia.org/wiki/Determ..._matrix_groups This makes verification to 2^64 easy. I/4 of odd n for n%8==5 and 8 Selfridges per test... Verified to 2^64 using Feitsma's list of 2PSPs. Last fiddled with by paulunderwood on 20220316 at 07:34 
20220316, 12:17  #14  
Feb 2017
Nowhere
1011111010100_{2} Posts 
Quote:
If Mod(Mod(1,n)*x + 1, x^4 + 1)^n == Mod(1  x, x^4 + 1) taking the norm gives (Mod(2, n))^n = 2. Quote:


20220316, 18:07  #15 
Sep 2002
Database er0rr
29×151 Posts 
FWIW, not a peep out of:
Code:
{forstep(n=5,1000000,8, if(!ispseudoprime(n), for(a=1,(n1)/2, if(gcd(a,n)==1, Det=Mod(a,n)^4+1; if(Det^n==Det&&Mod(Mod(x+a,n),x^4+1)^n==ax, print([n,a]))))));} Last fiddled with by paulunderwood on 20220316 at 18:16 
20220317, 01:29  #16  
Feb 2017
Nowhere
2^{2}×5^{2}×61 Posts 
Quote:
Mod(Mod(1,n)*x + 2, x^2 + 1)^(n+1) == 5 implies 5^(n1) == 1 (mod n) for n == 3 (mod 4) (assuming 5 does not divide n). That is, n is a Fermat pseudoprime to the base 5. I do not know if these have been as extensively computed as Fermat pseudoprimes to the base 2. But my guess is, even if they haven't been, if you run the base 5 test first, and only run Mod(Mod(x+2,n),x^2+1)^(n+1)==5 on the composite survivors, that will speed things up. 

20220317, 13:22  #17  
Sep 2002
Database er0rr
10433_{8} Posts 
Quote:


20220317, 14:06  #18 
Feb 2017
Nowhere
13724_{8} Posts 
Let
Code:
v=[Mod(1/4, x^4  4*x^3 + 6*x^2  4*x + 2), Mod(1/4*x^3 + 3/4*x^2  3/4*x + 1/4, x^4  4*x^3 + 6*x^2  4*x + 2), Mod(1/4*x^2 + 1/2*x  1/4, x^4  4*x^3 + 6*x^2  4*x + 2), Mod(1/4*x + 1/4, x^4  4*x^3 + 6*x^2  4*x + 2)]; The only really "nice" expression is for the constant term, trace(Mod(1/4,x^4  4*x^3 + 6*x^2  4*x + 2)*x^n). This may be expressed as Scratch that. The polynomial has two (complex conjugate) zeroes of absolute value sqrt(2 + sqrt(2)) and two of absolute value sqrt(2  sqrt(2)). The expression is zero for n == 4 (mod 8). What is true is that the nth root of the absolute value of the nth constant term has an upper limit of sqrt(2 + sqrt(2)). Note: The polynomial x^4  4*x^3 + 6*x^2  4*x + 2 is charpoly(Mod(x+1,x^4 + 1)). I wasn't advocating compiling a table of base5 pseudoprimes. I was merely thinking that most composites would "flunk" a base5 psp test, which (I am assuming) is much faster than the Mod(x+2,1+x^2) test. This would greatly reduce the number of slower Mod(2 + x, 1 + x^2) tests that needed to be done in searching for psp's for that test. Last fiddled with by Dr Sardonicus on 20220318 at 01:50 Reason: Fix bad notation;correct misstatement 
20220318, 15:02  #19 
Feb 2017
Nowhere
1011111010100_{2} Posts 
As you can see from the following, I have obtained closedform expressions for the coefficients of the degreelessthat4 lift of Mod(1 + x, 1 + x^4)^n. They can be written as 4term sums similar to the one already given. Unlike the constant term, though, the coefficient is a root of unity of degree greater than 1; a 4th or 8th root of unity. The trace may be written as a sum of algebraic conjugates; the conjugates of Mod(x, x^4 + 1) are Mod(x^3, x^4 + 1), Mod(x, x^4 + 1), and Mod(x^3, x^4 + 1). This allows the traces to be expressed as explicit 4term sums. These expressions are unlikely to be useful computationally, but may be helpful theoretically.
Code:
? for(n=0,15,v=[lift(Mod(x + 1, x^4 + 1)^n),trace(Mod(x, x^4 + 1)*Mod(1 + x, x^4+1)^n)/4, trace(Mod(x^2, x^4 + 1)*Mod(x + 1, x^4 + 1)^n)/4, trace(Mod(x^3, x^4 + 1)*Mod(x + 1, x^4 + 1)^n)/4, trace(Mod(x + 1, x^4 + 1)^n)/4];print(n" "v)) 0 [1, 0, 0, 0, 1] 1 [x + 1, 0, 0, 1, 1] 2 [x^2 + 2*x + 1, 0, 1, 2, 1] 3 [x^3 + 3*x^2 + 3*x + 1, 1, 3, 3, 1] 4 [4*x^3 + 6*x^2 + 4*x, 4, 6, 4, 0] 5 [10*x^3 + 10*x^2 + 4*x  4, 10, 10, 4, 4] 6 [20*x^3 + 14*x^2  14, 20, 14, 0, 14] 7 [34*x^3 + 14*x^2  14*x  34, 34, 14, 14, 34] 8 [48*x^3  48*x  68, 48, 0, 48, 68] 9 [48*x^3  48*x^2  116*x  116, 48, 48, 116, 116] 10 [164*x^2  232*x  164, 0, 164, 232, 164] 11 [164*x^3  396*x^2  396*x  164, 164, 396, 396, 164] 12 [560*x^3  792*x^2  560*x, 560, 792, 560, 0] 13 [1352*x^3  1352*x^2  560*x + 560, 1352, 1352, 560, 560] 14 [2704*x^3  1912*x^2 + 1912, 2704, 1912, 0, 1912] 15 [4616*x^3  1912*x^2 + 1912*x + 4616, 4616, 1912, 1912, 4616] EDIT: From the above data, you can see that for k == 6 (mod 8), the coefficient of x in lift((Mod(x + 1, x^4 + 1)^k) is zero; and if k == 4 (mod 8) the constant term is 0. I'm sure there's a straightforward proof, but I'm too lazy to work out the details It is thus impossible to have lift(lift((Mod(Mod(1,n)*x + 1, x^4 + 1)^k)) = 1  x for any n, if k is congruent to 4 or 6 (mod 8). Last fiddled with by Dr Sardonicus on 20220318 at 16:50 
20220320, 15:08  #20 
Feb 2017
Nowhere
2^{2}·5^{2}·61 Posts 
"That's the stupidest proof I've ever seen in my life!"
I finally thought of a very simple, straightforward proof of the "zeroness" of the coefficients of x^3, x^2, x and 1 in lift(Mod(x+1, x^4 + 1)^k) for k == 2, 0, 6 and 4 (mod 8) respectively.
All that is required is numerical verification that four consecutive values are 0. The rest being 0 then follows because for any given r, the subsequence lift(Mod(x+1,x^4 + 1))^(8*n + r) satisfies a linear recurrence with constant coefficients of order 4. Boom! Done. The characteristic polynomial is charpoly(Mod(x, x^4  4*x^3+6*x^24*x+2)^8)) = x^4 + 272*x^3 + 18528*x^2 + 4352*x + 256. The characteristic polynomial x^4 + 272*x^3 + 18528*x^2 + 4352*x + 256 factors as (x^2 + 136*x + 16)^2. I am too lazy to check whether any of the subsequences of terms in a residue class mod 8 actually satisfy a linear recurrence of order 2. 
20220320, 21:13  #21 
Sep 2002
Database er0rr
1000100011011_{2} Posts 
Powers of x over x^2136*x+16 are interesting.
Mod(Mod(x,n),x^2136*x+16)^(n+1)==16 is good for n%8==3 and n%8==5 I can also check Mod(Mod(x,n),x^2136*x+16)^((n+1)/4)==2 for n%8==3, and Mod(Mod(x,n),x^2136*x+16)^((n+1)/2)==4 for n%8==5. The test Mod(Mod(x,n),x^2136*x+16)^(n+1)==16 can be transformed into Mod(Mod(x,n),x^21154*x+1)^((n+1)/2)==1 for n%8={3, 5} for Fermat2PRP, making a quick check of Feitsma's 2^64 2PRP possible. As ever n%8==1 has psudoprimes. Without checking Feitsma, we now have simple tests for n%8 = {3,5,7} Last fiddled with by paulunderwood on 20220320 at 21:51 
20220321, 13:14  #22 
Feb 2017
Nowhere
2^{2}×5^{2}×61 Posts 
For every integer r = 0 to 7, the sequence a_{n} = lift(Mod(x+1,x^4+1)^(8*n + r)), n = 0, 1, 2, ... satisfies the recurrence a_{n+2}+136*a_{n+1} + 16*a_{n} = 0.
Thus, for any given r, the coefficients of 1, x, x^2 and x^3 in the lift are four sequences, each satisfying this recurrence. I have noted cases for even r where one of the four sequences is the zero sequence. I note that the discriminant of the quadratic x^2 + 136*x + 16 is 136^{2}  4*16 = 128*144 = 2*8^{2}*12^{2}. Note that Mod(1 + x, 1 + x^2)^4 has the linear minimum polynomial x + 4 (that is, (1 + I)^4 = 4), and now we have that Mod(1 + x, 1 + x^4)^8 has the quadratic minimum polynomial x^2 + 136*x + 16. Hmm, that's funny... I checked, and  sure enough! Mod(1 + x, 1 + x^8)^16 has a degree4 minimum polynomial; and Mod(1 + x, 1 + x^16)^32 has a degree8 minimum polynomial. I'm sold. Mod(1 + x, 1 + x^(2^{k}))^(2^{k+1}) has minimum polynomial of degree 2^{k1}. Hmm, in every case so far, the zeroes of the minimum polynomial are real... EDIT: Of course they're all real. And there's nothing special about powers of two. We have 1 + exp(2*I*pi/n) = exp(2*I*pi/(2*n))*[exp(2*I*pi/(2*n)) + exp(2*I*pi/(2*n))] = exp(2*I*pi/(2*n))*2*cos(2*pi/(2*n)). This is a 2nth root of unity times a real number. Raising to the nth power gives a real number. Last fiddled with by Dr Sardonicus on 20220321 at 13:39 