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.

Finding a splitting field of $x^3 + x +1$ over $\mathbb{Z}_2$.

Ok so originally I messed around with $x^3 + x +1$ for a bit looking for an easy way to factor it and eventually decided that the factors are probably made up of really messy nested roots. So then I tried looking at the quotient field $\mathbb{Z}_2[x]/x^3 + x + 1$ to see if I would get lucky and it would contain all three roots but it doesn't. Is there a clever way to easily find this splitting field besides using the cubic formula to find the roots and then just directly adjoining them to $\mathbb{Z}_2$?

Edit: Ok it turns out I miscalculated in my quotient field, $\mathbb{Z}_2[x]/x^3 + x + 1$ does contain all three roots.

share|improve this question
    
If degree is not $3$ it is $6$. –  André Nicolas Jul 3 '12 at 2:08
    
Actually, your quotient $\mathbb{Z}_2[x]/(x^3+x+1)$ does contain at least one root: $x$. This is because $x^3+x+1\equiv 0\pmod{x^3+x+1}$. Can you find the others? –  roninpro Jul 3 '12 at 2:08
add comment

3 Answers 3

up vote 5 down vote accepted

The splitting field is either degree $3$ or degree $6$ over $\mathbb{Z}_2$, hence it is either $\mathbb{F}_8$ or $\mathbb{F}_{64}$.

Let $\alpha$ be a root, so that $\mathbb{F}_8 = \mathbb{F}(\alpha)$. The elements are of the form $a+b\alpha+c\alpha^2$, with $\alpha^3=\alpha+1$.

Now, the question is whether any of these elements besides $\alpha$ is a root of the original polynomial $x^3+x+1$.

Note that $(\alpha^2)^3 = (\alpha^3)^2 = (\alpha+1)^2 = \alpha^2+1$, and so if we plug in $\alpha^2$ into the polynomial we have $$\alpha^6 + \alpha^2 + 1 = \alpha^2+1+\alpha^2+1= 0.$$ Thus, $\alpha^2$ is also a root. So the polynomial has at least two roots in $\mathbb{F}_8$, and so splits there.

share|improve this answer
    
oh shoot I must have miscaculated in my quotient field, ok cool, thanks! –  Ron Jeremy Jul 3 '12 at 2:11
add comment

Two good answers already here, but I wanted to emphasize the usefulness of the Frobenius endomorphism. Let $f(X) = X^3 + X + 1$. If I let $\alpha$ denote the image of $X$ in $k = \mathbb F_2[X]/(f(X))$ then applying Frobenius to $0 = f(\alpha)$ gives \[ 0 = (\alpha^3 + \alpha + 1)^2 = (\alpha^2)^3 + \alpha^2 + 1. \] Hence $\alpha^2$ is also a root of $f$, and $\alpha^2 \neq \alpha$ because $\alpha \neq 0, 1$. Since $k$ contains two roots of the cubic $f$, it contains three.

To bring in slightly more technology: extensions of finite fields are Galois and in particular normal, and this implies that if you adjoin one root of an irreducible polynomial over a finite field then you've actually adjoined all of them. This is, of course, not true in general!

share|improve this answer
    
Just wanted to add here, in $\Bbb{Z}_2(\alpha)[x]$, one can factor $x^3 + x + 1 = (x + \alpha)(x^2 + \alpha x + (\alpha^2 + 1))$. Given that $\alpha^2$ is also a root (as Dylan shows above), using ordinary high-school factorization techniques the third root is easily seen to be $\alpha^2 + \alpha$ (a somewhat preferable form than $\alpha^4$). That is: $x^2 + \alpha x + (\alpha^2 + 1) = (x + \alpha^2)(x + (\alpha^2 + \alpha))$ –  David Wheeler Jul 6 '12 at 10:20
add comment

If your cubic were to factor, the factorization must have at least one linear term, which corresponds to a root. It is easy to check it has no roots in $\mathbb{Z}_2$ - check them both! Plugging in $0$ and $1$ both give $1$ so are not roots, so your polynomial is irreducible over $\mathbb{Z}_2.$

A way to write the splitting field is $\mathbb{Z}_2(\alpha)$ where $\alpha$ is any one of the roots of $x^3+x+1.$ This is because $\alpha^2$ and $\alpha^4= \alpha^2+\alpha$ must then also be distinct roots of $x^3+x+1$, and these 3 then comprise a full list. Note, this isn't a special trick to notice for this problem. In fields of characteristic $p$, if $\beta$ is a root of a polynomial then $\beta^p$ will automatically also be a root, due to properties of the Frobenius endomorphism.

Or as roninpro pointed out in the comments, the quotient ring you considered (which is essentially the same thing as adjoining these roots) does contain at least one root, and by this same trick, all the roots.

share|improve this answer
    
I thought forming the quotient field adjoined just a single root? And that sometimes you would get lucky and the remaining roots could be formed within the quotient field as well, but that sometimes they couldn't, is this not correct? –  Ron Jeremy Jul 3 '12 at 2:17
    
@NollieTré You're correct. But extensions of finite fields are all Galois and in particular normal. So if $K/k$ are finite fields and $f \in k[X]$ is irreducible and has a root in $K$, then it splits in $K$. Frobenius is a great thing! –  Dylan Moreland Jul 3 '12 at 2:25
    
@NollieTré You are correct, sometimes the extra roots we find with the Frobenius trick just correspond to the same roots. But here they are distinct. You can check yourself (by carrying out the division) that here $x^2$ is also a root, since $x^6+x^2+1 = (x^3+x+1)(x^3-x-1)+2(x^2+x+1) = 0$, and similarly $x^4$ is also a root. So the quotient formed actually has all the roots. –  Ragib Zaman Jul 3 '12 at 2:26
    
Ok interesting, so is there a canonical example of when the quotient field does not contain all the roots of the polynomial? –  Ron Jeremy Jul 3 '12 at 2:29
    
I think it's easier to note that if $\alpha$ is a root of the polynomial then squaring gives $0^2 = (\alpha^3 + \alpha + 1)^2 = (\alpha^2)^3 + \alpha^2 + 1$. –  Dylan Moreland Jul 3 '12 at 2:30
show 4 more comments

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.