# Irreducibility of a Polynomial

## Homework Statement

Let ##f(x) = x^2 + x + 1 \in \Bbb{F}_2[x]##. Prove that ##f(x)## is irreducible and that ##f(x)## has a root ##\alpha \in \Bbb{F}_4##. Use the construction of ##\Bbb{F}_4## to display ##\alpha## explicitly

## Homework Equations

Definition: An element ##p## in a domain ##R## is irreducible if ##p## is neither ##0## nor a unit and, in every factorization ##p=uv##, either ##u## or ##v## is a unit.

Unless I am misunderstanding my book, ##\Bbb{F}_2 = \Bbb{Z}_2##, and ##\Bbb{F}_4## is the field of matrices of the form

$$\begin{bmatrix} a & b \\ b & a+b \\ \end{bmatrix}$$

where the entries come from ##\Bbb{F}_2##

## The Attempt at a Solution

For now I am focusing on the first part. Note that ##f(x)## is not the zero polynomial (zero element), nor is it a unit, since it is not a constant polynomial, which are the only units since ##\Bbb{F}_2## is a field and therefore ##\Bbb{F}_2[x]## is a domain. To see this, suppose that ##f(x)## is in fact a unit. Then there exists a ##u(x)## such ##1 = f(x) u(x)## which implies ##0 = \deg(1) = \deg(f) + deg(u)##, and therefore ##\deg(f) = 0##, which makes ##f(x)## the constant polynomial. But clearly this isn't the case, and so ##f(x)## cannot be a unit.

Now suppose that ##f(x) = u(x) v(x)## but ##v(x)## is not a unit. This is where I run into difficulties. I am trying to argue that ##u(x)## is a unit but I am having trouble. I could use a hint.

fresh_42
Mentor
You could factorize ##x^2+x+1## if a root ##a## is given. This will show you, whether ##f(x)## is irreducible or not and will also show that ##a## is in a quadratic extension of ##\mathbb{F}_2##.

So are you saying that if I have a root ##a## and can factorize ##f(x)## based upon this root, then this implies that every other factorization of ##f(x)## into ##u(x) v(x)## will be such that either ##u## or ##v## is a unit? Unfortunately I haven't learned about these ideas, nor the one about quadratic field extensions, yet.

Wait! Hold on! I do know a few things about irreducible polynomials. Since ##\Bbb{F}_2## is a field, I believe we can use the following theorem:

Let ##k## be a field and let ##f(x) \in k[x]## be a quadratic or cubic polynomial. Then ##f(x)## is irreducible if and only if ##f(x)## has no roots in ##k##.

Note that ##f(0) = 0^2 + 0 + 1 = 1 \neq 0## and ##f(1) = 1^2 + 1 + 1 = 3 = 1 \neq 0##, where ##0,1## are taken to be in ##\Bbb{F}_2##. This shows that the polynomial has no roots in ##\Bbb{F}_2## and is therefore irreducible. How does this sound?

As for the second part, what would be the best way to proceed? Should I just evaluate the polynomial ##f(x)## at these 2x2 matrices , interpreting ##1## as the identity matrix?

Edit, nevermind, just saw it's over Z_2

fresh_42
Mentor
I don't know how to calculate with those matrices. Looks a bit too complicated to me just to do calculations in ##\mathbb{F}_2 \oplus \mathbb{F}_2##, but the other argument is o.k.

I performed a long division ##(x^2+x+1):(x+a)## for a root ##a##, but it's basically the same: in order to be reducible it has to split into two linear parts, and this is impossible by substituting the two candidates.

Dick
Homework Helper
I don't know how to calculate with those matrices. Looks a bit too complicated to me just to do calculations in ##\mathbb{F}_2 \oplus \mathbb{F}_2##, but the other argument is o.k.

I performed a long division ##(x^2+x+1):(x+a)## for a root ##a##, but it's basically the same: in order to be reducible it has to split into two linear parts, and this is impossible by substituting the two candidates.

Isn't it pretty easy to calculate with those matrices? There's only four of them and one is zero and another is the identity.

fresh_42
Mentor
Isn't it pretty easy to calculate with those matrices? There's only four of them and one is zero and another is the identity.
Maybe. I'm just more used to ##\mathbb{F}_2[x]/(x^2+x+1)## than to ##\begin{bmatrix}a&b\\b&a+b\end{bmatrix}^2+\begin{bmatrix}a&b\\b&a+b\end{bmatrix}+\begin{bmatrix}1&0\\0&1\end{bmatrix}\,.## Might be a funny way to look at ##\mathbb{F}_4## but what to do with other field extensions? Or how to do a long division with those matrices?

Dick
Homework Helper
Maybe. I'm just more used to ##\mathbb{F}_2[x]/(x^2+x+1)## than to ##\begin{bmatrix}a&b\\b&a+b\end{bmatrix}^2+\begin{bmatrix}a&b\\b&a+b\end{bmatrix}+\begin{bmatrix}1&0\\0&1\end{bmatrix}\,.## Might be a funny way to look at ##\mathbb{F}_4## but what to do with other field extensions? Or how to do a long division with those matrices?

I really didn't think about the problem in general. I just wrote out the four matrices. ##\begin{bmatrix}1&1\\1&0\end{bmatrix}##, ##\begin{bmatrix}0&1\\1&1\end{bmatrix}##, zero and the identity and substituted them into the polynomial. You find the two roots you know you should find. So I didn't worry about dividing either (though there should be any essential problem once you figure out what is the inverse of what).

fresh_42
Mentor
Calculating ##g(x)## in ##f(x)=(x+a)\cdot g(x)## answers the entire question in one equation. To write ##a## as one of these matrices takes longer than to perform the division.

I really didn't think about the problem in general. I just wrote out the four matrices. ##\begin{bmatrix}1&1\\1&0\end{bmatrix}##, ##\begin{bmatrix}0&1\\1&1\end{bmatrix}##, zero and the identity and substituted them into the polynomial. You find the two roots you know you should find. So I didn't worry about dividing either (though there should be any essential problem once you figure out what is the inverse of what).

I go that

$$\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}$$

and

$$\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}$$

are roots of the polynomial. Is this what you found, Dick?

fresh_42
Mentor
They have to.

##f(x)## doesn't split over ##\mathbb{F}_2\,##, so ##a \notin \mathbb{F}_2 = \{0,1\}## and there must be two choices for ##a## as ##\deg f(x)=2\,## which leaves us with ##a## and ##a+1\,,## since ##\mathbb{F}_4=\{0,1,a,a+1\}.##

Dick