Let $K=\mathbb{Z}_2[x]/\langle x^4+x^2+x \rangle$ Find a $g\in K$ such that $g^2=x^3+x+1$ Let $K=\mathbb{Z}_2[x]/\langle x^4+x^2+x \rangle$. Find a $g\in K$ such that $g^2=x^3+x+1.$
I tried $x^3+x+1$ itself but unfortunately the degree is only $2$. I don't know how I can multiply something and get a polynomial of degree $3$.
 A: A nice trick to know.
$\newcommand{\d}{\frac{\mathbb Z_2[x]}{\langle x^4+x^2+x\rangle}}$In $\mathbb Z_2[x]$, we have the nice identity that $(a+b)^2 = a^2+2ab+b^2 = a^2+b^2$, because $2ab \equiv 0$ in $\mathbb Z_2[x]$! This naturally becomes $(a+b+c)^2 = a^2+b^2+c^2$ in $\mathbb Z_2[x]$ as well.
We can use this to great advantage as follows : let $p$ be an element satisfying $p^2 = x$ in the ring $\d$. Then $(p^3)^2 = x^3$ and $1^2 = 1$ therefore $(p^3+p+1)^2 = p^6+p^2+1 = x^3+x+1$ in $\d$.
So let's search for such a $p$ : $p^2 = x + h(x)(x^4+x^2+x)$ for some polynomial $h \in \mathbb Z_2[x]$. We start with the simplest $h$ (note $h = 0$ is not useful) , i.e. $h \equiv 1$. For this , we get the RHS as $$x^4+x^2+2x = x^4+x^2 = x^2(x^2+1) = x^2(x+1)^2 = [x(x+1)]^2$$
(The step $x^2+1 = (x+1)^2$ follows from the same $\mathbb Z_2$ identity I discussed earlier)
Et voilà! So $p = x(x+1)$, and $p^3+p+1$ provides the required square root.

Confirmation :
$$
p^3+p+1 = x^3(x+1)^3 + x(x+1)+1 = x^6 + x^5+x^4+x^3+x^2+x+1
$$
modulo $x^4+x^2 + x$ this reduces to $x^3+x+1$, whose square is in fact $(x^3+x+1)^2 = x^3+x+1$.
A: $K$ has $2^4$ elements:
$$ax^3+bx^2+cx+d, \ (a,b,c,d) \in {\mathbb{Z}_2}^4$$
We have $$g(0)^2=g(1)^2=1$$
So the only possible candidates for $g$ are
$$1\\
x^3+x^2+1\\
x^3+x+1\\
x^2+x+1
$$
First we calculate
$$x^4\equiv x^2+x$$
$$x^6\equiv (x^4+x^2+x)x^2 +x^4+x^3\equiv x^3+x^2+x$$
We can skip the constant polynomial $1$ immediately.  We use $$(a+b)^2=a^2+b^2 \bmod(2)$$
to check the remaining 3 candidates.
$$(x^3+x^2+1)^2=x^6+x^4+1=(x^3+x^2+x)+(x^2+x)+1=x^3+1$$
$$(x^3+x+1)^2=x^6+x^2+1=(x^3+x^2+x)+x^2+1=x^3+x+1$$
$$(x^2+x+1)^2=x^4+x^2+1=(x^2+x)+x^2+1=x+1$$
A: We use the identity $(u+v)^2=u^2+v^2.$ From $$x^4+x^2+x=0$$ we see that
$$x=x^4+x^2=(x^2)^2+x^2=(x^2+x)^2$$
And we can construct the root of an arbitrary polynomial
$$ax^3+bx^2+cx+d=x(ax^2+c)+bx^2+d=(x^2+x)^2(ax+c)^2+(bx+d)^2=((x^2+x)(ax+c)+(bx+d))^2=(ax^3+(a+c)x^2+(b+c)x+d)^2$$
So we see that every polynomial has exactly one square root.
A: The Quotient ring ${Z_2[x]/(x^4+x^2+x)}$ contains below elements.$${\{1,x,x^2,x^3,x^2+x,x^3+x^2,x^3+x^2+x,x+x^3\}}$$ if we square each of them, then we can see that for ${(x^2+x)^2=x}$, so  ${\sqrt{x}=(x^2+x)=p }$(as defined above by Teresa)

*

*now ${(x^3+x+1)^2= x^6+x^2+1= x^3+x^2+x+x^2+1=x^3+x+1}$
