Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $f(x) = x^6 + x + 1$ and define the field $F = \mathbb{Z}_2[x]/f(x)$

Compute the following in this field:

1. $(x^5 + x + 1)(x^3 + x^2 +1)$

I start by multiplying (in $\mathbb{Z}_2[x]$):

$(x^5 + x + 1)(x^3 + x^2 +1)$ = $(x^8 + x^7 + x^5 +x^4 + x^2 + x + 1)$

Then dividing the result with $f(x)$:

$(x^2 + x)$ and the remainder $(x^5 + x^4 + x^3 + x^2 + 1)$

Is this the right approach for solving this problem? Do I understand it correct that I want the result of my multiplication mod $f(x)$? Can I think of it as a simple modulus calculation:

$11$ mod $7 = a$

$7*1 + 4$ mod $7 = 4$

In my case I have

$(x^6 + x +1)*(x^2 + x) + \mbox{remainder}$ mod $(x^6 +x + 1) = \mbox{remainder}$

So my answer to the question would be the remainder, $(x^5 + x^4 + x^3 + x^2 + 1)$?

2. $(x + 1)^{-1}$

I read (wiki) that the inverse to $(x + 1)$ could be found by using the extended euclidean alg. for $a = (x^6 + x +1)$, $b = (x+1)$ but I don't really get it since $a$ is irreducible.

Any hints in the right direction would be appreciated!

share|cite|improve this question
up vote 2 down vote accepted

Your idea for (1) is correct.

As for (2), it is the same idea as for the ring of integers modulo $n$. The $gcd$ of $x+1$ and $x^6+x+1$ will be $1$ since $x+1$ and $x^6+x+1$ are coprime. Using the extended Euclidean algorithm you'll get $$ A(x+1) + B(x^6+x+1) = 1 $$ where $A, B \in \Bbb{F}_2[x]/f(x)$. So as you can see, modulo $x^6+x+1$ we have that $$ A(x+1) \equiv 1 \pmod{x^6+x+1} $$ and hence $A$ is the inverse of $x+1$.

NOTE: remember that in $\Bbb{Z}_2$ (which I hope you don't mean the $p$-adic integers), $-1 \equiv 1 \pmod{2}$.

share|cite|improve this answer
Thanks for the explanation, I think I understand it better now. $(x+1)(x^5 + x^4 + x^3 + x^2 + x) + 1$ was what I got but I wasn't sure that $(x^5 + x^4 + x^3 + x^2 + x)$ was the inverse, I see it now. – Sup3rgnu Jun 10 '12 at 23:26
About your note, you're right my answer in (1) should be $(x^5+x^4+x^3+x^2+1)$ since it's mod 2. – Sup3rgnu Jun 10 '12 at 23:41

Your first idea is right, and I think you need to read the extended Euclidean algorithm over again (because $x^6+x+1$ being irreducible should not deter you.)

Dividing $\frac{x^6+x+1}{x+1}$ you'll find $(x+1)(x^5+x^4+x^3+x^2+x)+1=x^6+x+1$, and so $(x+1)(x^5+x^4+x^3+x^2+x)=1$ in the quotient.

share|cite|improve this answer
Yeah I think I'm tired don't know what I was thinking.. That was what I got, just didn't see it. Thanks for the help! – Sup3rgnu Jun 10 '12 at 23:27

$\rm In\ \,{\it any}\,\ ring\ with\ \ \color{brown}{x^{2n}\! -\! x\! +\! 1} \,=\, 0\ $ one easily inverts $\rm\:1\!-\!x\:$ as follows

$\rm\quad\ \ \ \, \dfrac{1 }{1\!-\!x}\, =\, \dfrac{1\!\color{brown}{-\!x^{2n}\!+\!x\!-\!1}}{1-x}\, =\, \dfrac{1\!-\!x^{2n}}{1\!-\!x\ \ \ } - 1\, =\, x\! +\! x^2\! +\! x^3\! +\cdots + x^{2n-1}$

Generally $\rm\:g\:$ has such an "easy" inverse mod $\rm\:f\:$ when $\rm\:g\:|\:f\!-\!1\:$ since then $\rm\:f = 1 + h\,g,\:$ hence $\rm\: mod\ f\!:\,-h\,g \equiv 1,\:$ i.e. $\rm\:g^{-1} \equiv -h.\:$ The same is true if $\rm\:g\:|\:f\! -\! u\:$ for a unit $\rm\:u.\:$ When this is true, the extended Euclidean algorithm terminates in one step. This happens so frequently for "small" problems that it is well-worth testing before initiating the general algorithm.

share|cite|improve this answer

Your Answer


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.