Thread: mod x^4+1 View Single Post 2022-03-23, 13:01 #27 Dr Sardonicus   Feb 2017 Nowhere 599910 Posts If n == 3 (mod 8) is prime, then Mod(Mod(1,n)+x,x^4 + 1)^n == Mod(Mod(1,n) + Mod(1,n)*x^3, x^4 + 1) coefficients of x and x^2 are 0 If n == 5 (mod 8) is prime, then Mod(Mod(1,n)+x,x^4 + 1)^n == Mod(Mod(1,n) + Mod(-1,n)*x, x^4 + 1) coefficients of x^2 and x^3 are 0 If n == 7 (mod 8) is prime, then Mod(Mod(1,n)+x,x^4 + 1)^n == Mod(Mod(1,n) + Mod(-1,n)*x^3, x^4 + 1) coefficients of x and x^2 are 0 The condition that any of these congruences hold (mod n) implies that Mod(2,n)^n == Mod(2,n). Let lift(Mod(1+x, x^2 - 2)^k) = F[sub]k[sub]*x + Lk The "reduced" partial conditions that the "wrong" coefficients of Mod(Mod(1,n)+x, x^4 + 1)^n are zero, are: n == 3 (mod 8): n divides L(n+1)/2 n == 5 (mod 8): n divides F(n+1)/2 n == 7 (mod 8) n divides L(n-1)/2 The "reductions" are possible because they are conditions of divisibility by n, and n is odd. This allows one to ignore minus signs and powers of 2 in the relevant coefficients. The main part of getting rid of powers of 2 is to note that in the characteristic polynomial x^2 + 136*x + 16, substituting x = 4*x and dividing through by 16 gives x^2 + 34*x + 1. It is then a simple matter to figure out the correct power of 2 in the coefficients, divide it out, and match up the (absolute values of) two consecutive of the resulting odd numbers to coefficients below. Further substituting -x for x in x^2 + 34*x + 1 takes care of the minus signs, giving the polynomial x^2 - 34*x + 1. This is the characteristic polynomial of Mod(1+x, x^2 - 2)^4. Code: ? for(i=1,20,f=lift(Mod(1+x,x^2-2)^i);print(i" "f)) 1 x + 1 2 2*x + 3 3 5*x + 7 4 12*x + 17 5 29*x + 41 6 70*x + 99 7 169*x + 239 8 408*x + 577 9 985*x + 1393 10 2378*x + 3363 11 5741*x + 8119 12 13860*x + 19601 13 33461*x + 47321 14 80782*x + 114243 15 195025*x + 275807 16 470832*x + 665857 17 1136689*x + 1607521 18 2744210*x + 3880899 19 6625109*x + 9369319 20 15994428*x + 22619537 UPDATE: I figured out semi-reasonable formulations of the second partial conditions for n == 3, 5, and 7 (mod 8). In each case, the two conditions together are equivalent to your quartic condition. I saw no way to eliminate the powers of 2 from the second partial conditions. The F and L sequences are as above. I still cannot believe I figured out the second condition for n == 5 (mod 8). That one gave me fits! n == 3 (mod 8) n divides L(n+1)/2 and (-1)^((n-3)/8) * 2^((n-3)/4) * L(n-1)/2 == 1 (mod n) n == 5 (mod 8) n divides F(n+1)/2 and (-1)^((n+3)/8) * 2^((n+3)/4) * F(n-1)/4 * L(n-1)/4 == 1 (mod n) Note: Second condition can be restated as (-1)^((n+3)/8) * 2^((n-1)/4) * F(n-1)/2 == 1 (mod n) n == 7 (mod 8) n divides L(n-1)/2 and (-1)^((n+1)/8) * 2^((n-3)/4) * L(n+1)/2 == 1 (mod n) Last fiddled with by Dr Sardonicus on 2022-03-24 at 00:03 Reason: Forgot exponents! and update  