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.

I'm working through an assignment and need to write several elements as polyomials of degree <= 2.

($x^2+1$)($x+1$)

within the field

$\mathbb Z$$_3$[x] / ($x^3 + 2x + 1$)

And am unsure how exactly to go about doing this - could anyone give me some pointers as to what the question is asking me to do?

share|improve this question
    
If you have to do this a lot, it really pays to learn to use a "rewrite rule" as Bill Dubuque aptly calls it in his answer. Think about it this way. When you do arithmetic with complex numbers, you always rewrite $i^2=-1$. Here you do the same thing, and rewrite $x^3=-2x-1=x+2$. Consequently also $$x^4=x\cdot x^3=x(x+2)=x^2+2x$$ and so forth (much like $i^3=i\cdot i^2=i(-1)=-i$.) If you want to see several examples of this in the finite field $\mathbb{Z}_2[x]/(x^3+x+1)$, see the bottom half of my answer to this question. –  Jyrki Lahtonen Mar 29 '12 at 7:03

2 Answers 2

Divide the polynomial $(x^2+1)(x+1)$ (multiplied out) by the polynomial $x^3+2x+1$, remembering to work with the right field of coefficients. The remainder (or more properly, its equivalence class) is what you want.

How to do the division? Basically like ordinary polynomial division. $x^3+2x+1$ goes into $x^3+x^2+x+1$ (our product) once. Subtract. We get $(x^3+x^2+x+1)-(x^3+2x+1)$, which is $x^2-x$, or equivalently $x^2+2x$.

Another way: In this case, we can take a shortcut, well, maybe not a shortcut, just another way of thinking. The polynomial $x^3+2x+1$ is equivalent to $0$, so $x^3$ is equivalent to $-2x-1$. So $x^3+x^2+x+1$ is equivalent to $(-2x-1)+(x^2+x+1$, which simplifies to $x^2-x$, or, equivalently, $x^2+2x$.

share|improve this answer
    
Thanks! Exactly what I needed to know, also: wicked shortcut, really great way to re-think the problem. –  Stephen Young Mar 29 '12 at 6:49

Hint $\ $ In $\mathbb Z_3[x]/(x^3 + 2x + 1)$ we have $x^3 = -2x-1.\:$ This may be used as a rewrite rule which, iterated, suffices to reduce all polynomials to equivalent polynomials of degree $2$ or less. Namely, rewrite $x^{3+n}$ to $(-2x-1)\:x^n$ expand, and iterate, till all exponents are $< 3$. This is an equivalent way to calculate the remainder mod $\: x^3+2x+1$.

share|improve this answer

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.