# Fourth degree polynomial in $\mathbb Z_2[x]$ whose roots are the four elements of the field $\mathbb Z_2[x]/(x^2+x+1)$

As indicated by the title, I am supposed to find a fourth degree polynomial in $\mathbb Z_2[x]$ whose roots are the four elememts of the field $\mathbb Z_2[x]/(x^2+x+1)$. To me, the question doesn't really make sense. By definition, a root of a polynomial $f(x)\in \mathbb Z_2[x]$ is an element $a\in \mathbb Z_2$ such that the function $y \mapsto f(y)$ maps $a$ to $0$. However, the elements of $\mathbb Z_2[x]/(x^2+x+1)$ are classes of polynomials and not elements of $\mathbb Z_2$.

-

The natural embedding $\mathbb{Z}/2\mathbb{Z}\ \hookrightarrow\ (\mathbb{Z}/2\mathbb{Z})[x]$ induces an injection $$\mathbb{Z}/2\mathbb{Z}\ \hookrightarrow\ (\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1).$$ In this way we may consider $\mathbb{Z}/2\mathbb{Z}$ as a subring of $(\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1)$, which allows us to consider polynomials over $(\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1)$ with coefficients in $\mathbb{Z}/2\mathbb{Z}$. Colloquially they are reffered to as polynomials over $\mathbb{Z}/2\mathbb{Z}$, i.e. elements of $(\mathbb{Z}/2\mathbb{Z})[x]$.

Alternatively, the injection $\mathbb{Z}/2\mathbb{Z}\ \hookrightarrow\ (\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1)$ induces an injection $$(\mathbb{Z}/2\mathbb{Z})[y]\ \hookrightarrow\ ((\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1))[y],$$ and in this way $(\mathbb{Z}/2\mathbb{Z})[y]$ is naturally a subring of $((\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1))[y]$. Its consists of the polynomials (that have representatives) with coefficients in $\mathbb{Z}/2\mathbb{Z}$, which is why it is simply referred to as $(\mathbb{Z}/2\mathbb{Z})[y]$. The double use of the indeterminate $x$, both in $(\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1)$ and in $(\mathbb{Z}/2\mathbb{Z})[x]$, suggesting that $(\mathbb{Z}/2\mathbb{Z})[x]$ induces functions on $(\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1)$, may have confused you, as it did me.

So the question is to find a polynomial $f\in((\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1))[y]$ that is in the image of $(\mathbb{Z}/2\mathbb{Z})[y]$ under this natural injection, whose roots are the four elements of $(\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1)$.

-
Note that this argument holds for any (commutative) ring $R$ and any ideal $I\subset R[x]$ such that $I\cap R=(0)$. – Servaes Aug 22 '13 at 15:25

The nonzero elements of a field $F$ of order $q$ are a group under multiplication, hence each element has order dividing the group order, i.e. $a^{q-1}=1$ holds for all $a\ne 0$ or: All nonzero elements of $F$ are roots of the polynomial $X^{q-1}-1$. To make $0$ a root as well, multiply with $X$ to obtain $X^{q}-X$ as a polynomial having at least the $q$ elements of our field as roots - but by comparing the counts we see that the roots are exactly the elements of our field $F$.

-

Given an arbitrary field $\Bbb F,$ not all polynomials in $\Bbb F[x]$ will have roots in $\Bbb F$ (namely, if $\Bbb F$ is not algebraically closed). In such cases, we may want to adjoin roots for a given polynomial to $\Bbb F$, to get a larger field $\Bbb K$ in which the polynomial does have all of its roots.

In general, given a polynomial $f(x)\in\Bbb F[x]$ that is irreducible, we have that the ideal generated by $f$ is maximal, and so the quotient ring $\Bbb K:=\Bbb F[x]/(f)$ is a field. Let $\alpha$ denote the equivalence class of $x$ in this quotient ring. Note that there is a ready inclusion $\Bbb F\hookrightarrow\Bbb K,$ and it turns out that $$\Bbb K=\{c_0+c_1\alpha+\cdots+c_{n-1}\alpha^{n-1}\mid c_0,...,c_{n-1}\in\Bbb F\},$$ where $n$ is the degree of $f$. Furthermore, $f(\alpha)$ is clearly the equivalence class of $f(x)$ in $\Bbb K,$ and so is $0$ in $\Bbb K.$ Suddenly, we have a root where there was none before!

Let me give you a more common example: Consider $\Bbb F=\Bbb R$ and $f(x)=x^2+1,$ put $\Bbb K=\Bbb F[x]/(f),$ and let $i$ be the equivalence class of $x$ in $\Bbb K$. Then $$\Bbb K=\{a+bi\mid a,b\in\Bbb F\},$$ and $i$ has the property that $i^2=-1$! This, then, is just another way to construct the complex numbers.

Let us now consider your particular example. Letting $f(x)=x^2+x+1,$ and letting $\alpha$ be the equivalence class of $x$ in $\Bbb K=\Bbb Z_2[x]/(f),$ we have $$\Bbb K=\{0,1,\alpha,1+\alpha\},$$ and $\alpha^2+\alpha+1=0.$ How many roots does $f(x)$ have in $\Bbb K$? Well, we know that $\alpha$ is a root, and certainly $0,1$ are not roots, but what about $1+\alpha$? Indeed, \begin{align}f(1+\alpha) &= (1+\alpha)^2+(1+\alpha)+1\\ &= 1+2\alpha+\alpha^2+1+\alpha+1\\ &= \alpha^2+\alpha+1\qquad(\text{since }2=0)\\ &= 0,\end{align} so $\alpha$ and $1+\alpha$ are roots of $f(x)$ in $\Bbb K$. Can you figure out how to make the desired polynomial, then?

As an alternate approach, note that the three non-zero elements of $\Bbb K$ form a group under multiplication, so each of them has multiplicative order dividing $3,$ meaning that $a^3=1$ for each non-zero $a\in\Bbb K.$ Hence, $x^3-1$ is a polynomial of which all three non-zero elements of $\Bbb K$ are roots, so $x^4-x$ is a polynomial of which all elements of $\Bbb K$ are roots. (More generally, for any finite field of order $q,$ $x^q-x$ is a polynomial of which all elements of the field are roots.) Rewriting this as a polynomial with $\Bbb Z_2$ coefficients gets us $x^4+x,$ the desired answer.

-
Thank you for your reply! The funny thing is however, that in the book I am using (Hungerford) this question turns up before any such discussion of extension fields. – Alexandre Vandermonde Aug 22 '13 at 15:29
That is peculiar. – Cameron Buie Aug 22 '13 at 15:33
$cx(x-1)(x-\alpha)(x-1-\alpha)$ for any (nonzero) $c\in F$? – Alexandre Vandermonde Aug 22 '13 at 15:34
That works over $\Bbb K$, of course, but bear in mind that $\alpha$ is not an element of $\Bbb F=\Bbb Z_2,$ and that there is only one non-zero $c\in\Bbb F.$ The best you're going to get for a factorization over $\Bbb F$ is $$x(x-1)(x^2+x+1).$$ – Cameron Buie Aug 22 '13 at 15:36
Alright, thanks! I will probably come back to this question after reading the chapters on extension fields. – Alexandre Vandermonde Aug 22 '13 at 15:46