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.

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|improve this question
add comment

3 Answers

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|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
add comment

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|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
add comment

$\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|improve this answer
add comment

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.