Thread: mod x^4+1
View Single Post
Old 2022-03-23, 13:01   #27
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

599910 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote