# Inverse element of $x^2 + x + 1$ in $\mathbb Z_2[x]/\langle x^3 + x + 1\rangle$

I know that $$\mathbb Z_2[x]/\langle x^3 + x + 1\rangle$$ is a field since $$x^3 + x + 1$$ is irreducible in $$\mathbb Z_2$$. But I still can't seem to find any inverse element for $$x^2 + x + 1$$. I want to find an element $$g(x) \in \mathbb Z_2[x]/\langle x^3 + x + 1\rangle$$ such that $$(x^2 + x + 1)g(x) = 1$$. I've tried multiplying every single element of $$\mathbb Z_2[x]/\langle x^3 + x + 1\rangle$$ by $$x^2 + x + 1$$, but I never seem to get any of them to be equal to 1 or equivalent. How is this possible if $$\mathbb Z_2[x]/\langle x^3 + x + 1\rangle$$ is a field?

• Use the Euclidean algorithm to find $a,b\in \mathbb{Z}_2[x]$ so that $a(x^2+x+1) + b(x^3+x+1) = 1$, then $a$ is the inverse Commented Oct 15, 2019 at 6:21
• @vujazzman Technically that's the extended euclidean algorithm. Also, that's an answer, not a comment, so it would be better if you put it as an answer rather than as a comment. Commented Oct 15, 2019 at 6:30
• Is it considered an answer if it is only a hint to an answer and not the actual answer? Commented Oct 15, 2019 at 6:31
• @vujazzman That's not a hint. It's basically a full solution with just some rote calculation left to do. In my opinion, a "hint" should leave most of the actual thinking, and just be a nudge in the right direction (in this case, I don't even know how to write an actual hint that doesn't give it all away). And yes, hints are answers. Comments are for asking for clarification, pointing out possible typos, and so on. Commented Oct 15, 2019 at 7:11

Use the Euclidean algorithm to find $$a,b \in \mathbb{Z}_2[x]$$ so that $$a(x^2+x+1)+b(x^3+x+1) = 1$$. Then $$a$$ is the inverse.

Well, the extended Euclidean algorithm provides the solution.

I will present another way doing it:

The field $$GF(8)=\Bbb Z_2[x]/\langle x^3+x+1\rangle$$ has the elements

$$0,1,\alpha,\alpha^2,\alpha^3=\alpha+1,\alpha^4=\alpha^2+\alpha,\alpha^5=\alpha^2+\alpha+1,\alpha^6=\alpha^2+1,\alpha^7=1,$$

where $$\alpha$$ is a zero of $$x^3+x+1$$.

The inverse of $$\alpha^2+\alpha+1$$ you can get

(1) by recognizing that $$\alpha^5=\alpha^2+\alpha+1$$ and so $$(\alpha^5)^{-1} =\alpha^2$$, since $$\alpha^7=1$$,

or

(2) by solving the equation

$$(\alpha^2+\alpha+1)\cdot (a\alpha^2+b\alpha +c)=1$$

for $$a,b,c\in\Bbb Z_2$$.

• first part of your answer is ok. But I can't understand why $(\alpha^2+\alpha+1)(a\alpha^2+b \alpha+c)=1$? Specially why you take $(a\alpha^2+b \alpha+c)$? i.e., why $a,b$?
– MAS
Commented Oct 15, 2019 at 8:15
• @M.A.SARKAR The multiplication of $\alpha^2+\alpha+1$ with the inverse must be $1$. Multiply out. This will allow you to determine the coefficients $a,b,c,$. Commented Oct 15, 2019 at 8:19
• This aged mathematician with failing vision begs you: Please Do Not Use Both $a$ And $\alpha$ in the same formula, or even in close proximity to each other in any exposition. Commented Oct 15, 2019 at 15:54

Let $$a$$ be the value of $$x$$ modulo the ideal $$(x^3+x+1)$$ in $$\Bbb F_2[x]$$. We have to compute the inverse of $$(a^2+a+1)$$ in the field $$\Bbb F_2(a)$$. This inverse is $$a^2$$, quick check: $$a^2(a^2+a+1)=a(a^3+a^2+a)=a(a+1+a^2+a)=a(a^2+1)=a^3+a=1\ .$$

Write $$(x^2+x+1)(ax^2+bx+c)=1\implies ax^4+(a+b)x^3+(a+b+c)x^2+(b+c)x+c=a(-x^2-x)+(a+b)(-x-1)+(a+b+c)x^2+(b+c)x+c=(b+c)x^2+cx+c=(b+c)x^2+cx+c-a=1\implies a=1,b=0,c=0$$, where I have used the fact that $$x^3+x+1=0$$ to substitute for $$x^4$$ and $$x^3$$.

So $$x^2$$ is your inverse.

• One can find a solution that way but if you want this to be an answer it requires some more formatting and some text explanation. Commented Oct 15, 2019 at 6:39

Really, now, your field contains only eight elements, and since its multiplicative group has seven elements, it is cyclic. In other words, any element different from $$1$$ will generate.

Why don’t you buckle down and simply, pencil in hand, write down the successive powers of, for instance, $$x$$? You get $$1$$, $$x$$, $$x^2$$, $$x^3=x+1$$, et cetera. It’ll take you only a few moments to finish.