Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

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

share|improve this answer
    
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$.

share|improve this answer

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.

share|improve this 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
2  
$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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.