# Thread: Factor x^16+x as a product of irreducible polynomials

1. ## Factor x^16+x as a product of irreducible polynomials

Factor x^16+x as a product of irreducible polynomials in Z2[x].

2. ## Re: Factor x^16+x as a product of irreducible polynomials

well, ONE factor is obvious: x.

x16 + x = x(x15 + 1).

so now we just need to factor x15 + 1 in Z2[x].

note that x15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1).

we can factor x3 + 1 as (x + 1)(x2 + x + 1) <---two irreducible factors (why?)

so now we just have to factor:x12 + x9 + x6 + x3 + 1.

note that: x15 + 1 also factors as (x5 + 1)(x10 + x5 + 1).

since x2 + x + 1 is an irreducible factor, it must divide either x5 + 1 or x10 + x5 + 1. prove it doesn't divide x5 + 1.

we can further factor x5 + 1 as (x + 1)(x4 + x3 + x2 + x + 1).

prove that the quartic is irreducible (hint: it suffices to show it has no linear or quadratic factors).

use long division to determine the quotient (xx10 + x5 + 1)/(x2 + x + 1).

argue that since GF(16) is every root of x16 - x, and GF(8) is a subfield of GF(16), there must be an irreducible factor of x16 - x of degree 8 (we've already found the irreducible factors of orders 1,2 and 4). why does this mean we're done?