Irreducibility of a Polynomial

  • Thread starter Bashyboy
  • Start date
  • #1
1,421
5

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.
 

Answers and Replies

  • #2
15,561
13,673
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##.
 
  • #3
1,421
5
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.
 
  • #4
1,421
5
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?
 
  • #5
840
14
Edit, nevermind, just saw it's over Z_2
 
  • #6
15,561
13,673
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.
 
  • #7
Dick
Science Advisor
Homework Helper
26,263
619
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.
 
  • #8
15,561
13,673
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?
 
  • #9
Dick
Science Advisor
Homework Helper
26,263
619
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).
 
  • #10
15,561
13,673
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.
 
  • #11
1,421
5
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?
 
  • #12
15,561
13,673
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\}.##
 
  • #13
Dick
Science Advisor
Homework Helper
26,263
619

Related Threads on Irreducibility of a Polynomial

  • Last Post
Replies
5
Views
1K
Replies
1
Views
2K
Replies
2
Views
3K
Replies
3
Views
2K
Replies
5
Views
2K
Replies
11
Views
1K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
2
Views
858
Replies
1
Views
4K
I
Top