5
$\begingroup$

Find all irreducible polynomials of degrees 1,2 and 4 over $\mathbb{F_2}$.

Attempt: Suppose $f(x) = x^4 + a_3x^3 + a_2x^2 + a_1x + a_0 \in \mathbb{F_2}[x]$. Then since $\mathbb{F_2} =${$0,1$}, then we have either $0$ or $1$ for each $a_i$. Then we have two choices for the $4$ coefficients, hence there are 16 polynomials of degree $4$ in $\mathbb{F_2}[x]$.

Recall $f(x)$ is irreducible if and only if it has not roots. Then

$f_1 = x$ is irreducible because it has not roots

$f_2 = x + 1$ is also another irreducible polynomial.

$f_3 = x^4 + x^2 + x = x ( x^3 + x + 1) $ is reducible.

$f_4 = x^4 = x^3* x$ is reducible

$f_5 = x^4 + x + 1$

Can someone please help me? Is there a way I can save time in finding the irreducible polynomials, other than just trying to come up with polynomials. Any better approach or hint would really help! Thank you !

$\endgroup$
  • 1
    $\begingroup$ *"Recall $f(x)$ is irreducible if and only if it has not roots." This is false; the polynomial $x^4+x^2+1$ is reducible but as no roots. $\endgroup$ – Servaes Dec 7 '15 at 2:56
  • 1
    $\begingroup$ "$f(x)$ is irreducible if and only if it has no roots" - not true. For example $(x^2+x+1)^2$ has no roots but is reducible. $\endgroup$ – David Dec 7 '15 at 2:56
  • 3
    $\begingroup$ Degree $1$, every polynomial is irreducible, there are two. Degree $2$, irreducible iff it has no roots, easy, only $x^2+x+1$. Degree $4$ is tougher, a polynomial can be reducible but have no roots. $\endgroup$ – André Nicolas Dec 7 '15 at 2:57
  • $\begingroup$ Enlisting and checking gives 3 polynomials of degree 4. However, I'm also interested in a quick way as OP has asked. $\endgroup$ – Shailesh Dec 7 '15 at 2:59
7
$\begingroup$

Degree $1$, clearly $x$ and $x+1$.

Degree $2$, notice the last coefficient must be one, so there are only two options, $x^2+x+1$ and $x^2+1$. Clearly only $x^2+x+1$ is irreducible.

Degree $4$. There are $8$ polynomials to consider, again, because the last coefficient is $1$, now notice a polynomial is divisible by $x+1$ if and only if the sum of its coefficients is even. So the only polynomials without factors of degree $1$ are four:

$x^4+x^3+x^2+x+1$

$x^4+x^3+1$

$x^4+x^2+1$

$x^4+x+1$.

Of course, we are missing the possibility it is the product of two irreducibles of degree $2$, but the only combination is $(x^2+x+1)(x^2+x+1)=x^4+x^2+1$.

Hence the irreducible ones are:

$x^4+x^3+x^2+x+1,x^4+x^3+1,x^4+x+1$

$\endgroup$
  • $\begingroup$ So we can say $f = x^4 + x + 1 $ is irreducible because it has not quadratic factors. In general not all polynomials of degree 4 will be reducible $x^4 + x^2 + x + 1$ is reducible because it has one root . $\endgroup$ – Mahidevran Dec 7 '15 at 3:23
  • $\begingroup$ Yeah, it is divisible by $x+1$ (in other words $1$ is a root). $\endgroup$ – Jorge Fernández Hidalgo Dec 7 '15 at 3:38
  • $\begingroup$ Just something to help others reading this answer who might have been initially confused as I was: "a polynomial is divisible by $x+1$ if and only if the sum of its coefficients is even" this comes from the Remainder Theorem since in $\mathbb{F}_2$ anything even mods to zero. $\endgroup$ – Raj Apr 8 at 18:28
2
$\begingroup$

$f_1$ is irreducible because $f_1 (0)=a0\equiv_2 0$. We cannot have an irreducible polynomial of degree one because we must have that $a=1$(otherwise it is constant), and $ax+1$ has $1$ as a solution. If our constant term is zero, then we have the root $0$ as described above.

Now for polynomials of degree 2, we want to determine when $ax^2+bx+c\equiv_2 0$. We plug in both $0$ and $1$ to obtain that $c$ is not equivalent to $0$ mod $2$ (so it must be $1$), and that $a+b+1$ is also not equivalent to $0$ mod $2$. This tells us that polynomial must be of the form $x^2+x+1$, because if either $a $ or $b $ were $0$ then it would have a solution of $x=1$.

Perform this same reasoning process for 4th degree polyomials.

$\endgroup$
  • 1
    $\begingroup$ Except fourth degree can factor into irreducible quadratics, so eliminate that possibility first. $\endgroup$ – Macavity Dec 7 '15 at 3:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.