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

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$.
• If $f(x)=x^4+x+1$, then what about $f(\frac1x)$, respectively $f(\frac1x+1)$? – user26857 May 3 '16 at 9:36
• 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? – M47145 May 3 '16 at 19:32
• @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$? – user26857 May 3 '16 at 20:37
• 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$? – M47145 May 3 '16 at 21:30
• 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$. – user26857 May 3 '16 at 21:37