Discrete Math Help

Math wizards, I know you're out there somewhere.

divide the polynomials in Z2
I think

I think that there is only one factorization since Z2 is a field.

So we have x+1 as a factor and divide x^12 + 1 by it.

x^12 + 1 = (x + 1)(x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1) = (x + 1)p(x)

Since the number of summands in p(x) is even, p(1) = 0 and (x+1) is again a factor.

p(x) = (x+1)(x^10 + x^8 + x^6 + x^4 + x^2 + 1) = (x+1)q(x)

and again

q(x) = (x+1)(x^9 + x+8 + x^5 + x^4 + x + 1) = (x+1)r(x)

and again

r(x) = (x + 1)(x^8 + x^4 + 1) = (x + 1)s(x)

Now we need to check s(x) for quadratic factors. The only irreducible quadratic factor is x^2 + x + 1 since x^2 = x x, x^2 + 1 = (x+1)(x+1), x^2 + x = x(x + 1).

x^8 + x^4 + 1 = (x^2 + x + 1)(x^6 + x^5 + x^3 + x + 1)
x^7 + x^6 + x^4 + 1
x^5 + x^4 + 1
x^3 + 1
x^2 + x + 1
0

So x^2 + x + 1 is another factor, and again:

x^6 + x^5 + x^3 + x + 1 = (x^2 + x + 1)(x^4 + x^2 +1)

Since (x^2 + x + 1)^2 = x^4 + x^2 + 1 we have finished.

x^12 + 1 = (x + 1)^4 (x^2 + x + 1)^4

>>75442
The last step can be simplified:

Since (x^2 + x + 1)^2 = x^4 + x^2 + 1 = z^2 + z + 1 for z = x^2:

s(x) = x^8 + x^4 + 1 = z^4 + z^2 + 1 = (z^2 + z + 1)^2 = ((x^2 + x + 1)^2)^2 = (x^2 + x + 1)^4

>>75185
(x^12+1)
(x^6+1)(x^6+1)
(x^3+1)(x^3+1)(x^6+1)
(x^3+1)(x^3+1)(x^3+1)(x^3+1)
(x+1)(x^2+x+1)(x^3+1)(x^3+1)(x^3+1)
(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x^3+1)(x^3+1)
(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x^3+1)
(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x+1)(x^2+x+1)

>>75442
>>75583

Thanks, anons.

Wasn't sure I was doing it right.

What about x^5-2x4+x3-2x2+x-2 mod 3, 5 or 7?

Z3 for example, f(1) = -3 = 0 and f(2) = 0. So x+1 and x+2 are factors. I divide and get the quotient, but it doesn't divide by these factors anymore.

It ends up factoring to (x+1)^3(x+2)^2 mod 3 somehow but I don't know how to get there.

>>75718
I would first multiply the two factors:

(x+1)(x+2) = x^2 + 3x + 2 = x^2 + 2 (mod 3)

and then divide:
x^5 - 2x^4 + x^3 - 2x^2 + x - 2 =
x^5 + x^4 + x^3 + x^2 + x + 1 =
(x^2 + 2)(x^3 + x^2 - x - 1)

and again:
x^3 + x^2 - x - 1 = (x^2 + 2)(x + 1)

f(x) = (x^2 + 2)^2(x + 1) = (x+2)^2(x+1)^3

>>75786
A more general solution is to factorize f(x) in the integers and then look at the factors modulo 3,5,7:

x^5 - 2x^4 + x^3 - 2x^2 + x - 2 =
(x - 2)(x^4 + x^2 + 1)

Since x^4 + x^2 + 1 > 0 there are no further zeros in Z which means that x^4 + x^2 + 1 can only be the product of two irreducible quadratic functions or be irreducible itself.

(x^2 + ax + 1)(x^2 + bx + 1) = x^4 + (a+b)x^3 + (ab+2)x^2 +(a+b)x + 1

Since a+b = 0, b = -a which implies ab+2 = -a^2 + 2 = 1, that is, a = +-1 and b = -+1

f(x) = (x-2)(x^2 + x + 1)(x^2 - x + 1)

Now you can check the quadratic functions modulo 3,5,7.

>>75786
>>75805

Awesome, thanks again.

I haven't learned about the general solution strat yet, but your post cleared it up.