Quartic polynomial in $\Bbb{F}_2[x]$ whose roots are the four elements of the field $\Bbb{F}_2[x]/(x^2+x+1)$

Question

As indicated by the title, I am supposed to find a quartic polynomial in $\mathbb F_2[x]$ whose roots are the four elements of the field $\mathbb F_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 F_2[x]$ is an element $a\in \mathbb F_2$ such that the function $y \mapsto f(y)$ maps $a$ to $0$. However, the elements of $\mathbb F_2[x]/(x^2+x+1)$ are classes of polynomials and not elements of $\mathbb F_2$.

Answer 1

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.

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

Answer 3

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