# finite fields factorization

Let $\mathbb{F}_2$ be the finite field with two elements. Let $f(x) = x^6+x^4+x+1$ be in $\mathbb{F}_2[x]$. If $f(x)$ is irreducible, give a reason. If it is not irreducible, determine a factorization of $f$ into irreducible monic polynomials in $\mathbb{F}_2[x]$.

-
What is your question? What have you tried? –  Álvaro Lozano-Robledo Dec 13 '11 at 19:46
@user21175: Welcome to Math.SE. For future reference, please known that it is polite to ask a question rather than assign the community a problem. It is also good practice to specify any difficulties you have had with a problem, or to explain what you tried, and where you are stuck. –  JavaMan Dec 13 '11 at 19:47
Never a bad idea to check whether this has a root in your ground field, and there are only two elements there to check. Is $1$ a root, for example? –  Dylan Moreland Dec 13 '11 at 19:57

EDIT: Given that the full answer has been posted, I've edited to include all stages (as opposed to the outline of a method, which I previously posted)

The following looks longer than it should, since I decided to write out each stage fully to help you get a feel for what's going on. In practice, I would write a lot, lot less down.

i) Does $f$ have any roots in $\mathbb{F}_2$? This should always be your first consideration, as if the answer is "yes" we immediately get that $f$ is not irreducible as we can split out a linear factor.

$\mathbb{F}_2$ is nice, as its only elements are $0$ and $1$, and we have that $1+1=0$. This means we only have two potential roots to check: $f(0) = 1$ is no good, but $f(1) = 1 + 1 + 1 + 1 = 0$ tells us that $1$ is a root of $f$, so $(x-1) = (x+1)$ is a factor and $f$ is not irreducible.

ii) Now you need to find the other factor of $f$ that corresponds to $(x+1)$.

Clearly it must be of the form $(x^5 + ax^4 + bx^3 + cx^2 + dx + 1)$, since we need the first and last coefficients of the product of this quintic with $(x+1)$ to be $1$. Considering the coefficient of $x^5$ gives $a = 1$. Considering $x^4$ gives $b = 1$. Continuing this process gives $f = (x+1)(x^5 + x^4 + 1)$ (you could have used polynomial long division instead of comparing coefficients here, but since there are only 2 elements in our field it's really easy to use the above method - after a little practice, you won't even have to write anything down).

iii) Clearly $(x+1)$ is irreducible, since it has degree $1$. What about $(x^5 + x^4 + 1)$?

Neither $1$ nor $0$ are roots, so it's either irreducible or it has a quadratic and a cubic factor. You could now use the same method as in ii), by writing $(x^5 + x^4 + 1) = (x^3 + ax^2 + bx + 1)(x^2 + cx + 1)$ and equating coefficients. It turns out that we get $(x^5 + x^4 + 1) = (x^3 + x + 1)(x^2 + x + 1)$ (if we couldn't find coefficients to make it work, then we would have shown that the quintic is irreducible).

iv) So far we have $f = (x+1)(x^2 + x + 1)(x^3 + x + 1)$. Can we reduce it any further?

The answer is no, since if we could then we must have another linear factor of $f$, which we know isn't possible since we already determined our quintic factor (and so now our quadratic and cubic factors) have no roots in $\mathbb{F}_2$.

-
As one more trick in iii), since $(x^2+1) = (x+1)^2$ in $\mathbb F_2[x]$, the only quadratic that we need to check is $x^2 + x + 1$. –  Dilip Sarwate Dec 13 '11 at 20:53
+1 IOW $x+1$ is the only irreducible polynomial in $F_2[x]$ with an even number of terms. –  Jyrki Lahtonen Dec 14 '11 at 17:40

What are the roots of the polynomial? For each root $x_0$, you can divide out a factor $x-x_0$. Check that what's left doesn't have any roots. That means it has no linear factors. So you can deduce from its degree that there's only one combination of degrees that might allow it to be written as a product of two factors. If you write the leading terms of these factors and also see that they must both have constant term $1$ to produce the $1$ in their product, you can then deduce the rest of the terms.

-

$$f(x)=x^6+x^4+x+1=(1+x^3)(1+x+x^3)=(x+1)(1+x+x^2)(1+x+x^3)$$

1. $1+x$ is irreducible, since it has degree one
2. Suppose $1+x+x^2=(x+a)(x+b)=x^2+(a+b)x+ab$. Then $ab=1 \Rightarrow a = b = 1$ gives a contradiction.
3. $1+x+x^3=(x^2+x+a)(x+b)=x^3+(1+b)x^2+(a+b)x+ab$. Then again $ab=1 \Rightarrow a=b=1$ gives a contradiction.

Can you see why we needn't consider the case $(x+a)(x+b)(x+c)$ in 3.?

-