Irreducibility of a Polynomial

[Bashyboy]

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]

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$.

 

[Bashyboy]

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.

 

[Bashyboy]

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?

 

[qspeechc]

Edit, nevermind, just saw it's over Z_2

 

[fresh_42]

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]

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]

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]

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]

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.

 

[Bashyboy]

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]

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]

Is this what you found, Dick?

Sure.