The problem:

Show that every polynomial of degree $1,2,$ or $4$ in $\mathbb{Z}_2[x]$ has a root in $\mathbb{Z}_2[x]/(x^4+x+1)$.

My attempt:

I know that the polynomials $x$ and $x+1$ have roots $[0]$ and $[1]$ respectively in $\mathbb{Z}_2[x]/(x^4+x+1)$.

Polynomials of degree 2 that are reducible in $\mathbb{Z}_2[x]$ clearly have roots so it remains to check the ones that are irreducible. The only irreducible polynomial of second degree in $\mathbb{Z}_2[x]$ is $x^2+x+1$ and it has root $[x^2+x+1]$ since $[x^2+x+1]^2+[x^2+x+1]+1=[x^4+x^2+1+x^2+x+1+1]=[x^4+x+1]=[0]$.

In degree four is where I have trouble. The reducible ones clearly have roots, and I've narrowed down the irreducible ones to $x^4+x+1$, $x^4+x^3+1$ and $x^4+x^3+x^2+x+1$. The first one is clear since it has the root $[x]$. I'm confused at the last two. I know I could brute force the answer by plugging in each possible $[a_3x^3+a_2x^2+a_1x+a_0]$ into $x^4+x+1$ and check by long division if the resulting polynomial is congruent to $[0]$, but somehow I suspect that isn't the intended method. However, I can't think of anything better either.

Would someone care to give me a hint? Thanks!


Hints. If $a=x\bmod (x^4+x+1)$, then try $a^{-1}$ for $x^4+x^3+1$, and $a^{-1}+1$ for $x^4+x^3+x^2+x+1$.

  • $\begingroup$ If $f(x)=x^4+x+1$, then what about $f(\frac1x)$, respectively $f(\frac1x+1)$? $\endgroup$
    – user26857
    May 3 '16 at 9:36
  • $\begingroup$ I can see that $a^{-1}$ and $a^{-1}+1$ work, but I'm not entirely sure how you got them. I see that $f(\frac{1}{x})=\frac{1}{x^4}(1+x^3+x^4)$, but does that help me? $\endgroup$
    – M47145
    May 3 '16 at 19:32
  • $\begingroup$ @M47145 If $f(\frac{1}{x})=\frac{1}{x^4}(1+x^3+x^4)$ and $f(a)=0$, then what happens if one evaluates $x$ at $\frac1a$? $\endgroup$
    – user26857
    May 3 '16 at 20:37
  • $\begingroup$ Ok, letting $x=1/a$ I get that $f(a)=a^4(1+x^3+x^4)=0$ so either $a^4=0$ or $1+x^3+x^4=0$. But we know that $a\neq 0$ so the former case is impossible. Thus $1+x^3+x^4=0$. But I don't see how you can intuitively come up with that. For example why would I test $f(\frac{1}{x}+1)$ rather than say $f(\frac{1}{x^2}+1)$ for the polynomial $x^4+x^3+x^2+x+1$? $\endgroup$
    – M47145
    May 3 '16 at 21:30
  • 1
    $\begingroup$ Well, I don't think I have a recipe for this. I can tell you how I did it: for the first it was easy, while for the second I was guided by the first. Once we have a root for $x^4+x^3+1$ then we need two more terms in order to get $x^4+x^3+x^2+x+1$. These show up immediately if replace $x$ by $x+1$ in $x^4+x^3+1$. $\endgroup$
    – user26857
    May 3 '16 at 21:37

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.