# What is the congruence class of $x^3\mod x^3+x+1$?

I have a given Polynom congruence with a Polynom $x^3+x+1$ ... so the set of the congruence classes is $\{0, 1,x,x+1,x^2,x^2+1,x^2+x,x^2+x+1\}$

But what would look this like? $$x^3\mod x^3+x+1\equiv ?$$
I think the result must be one of the congruence classes of the set, mentioned above, but I cannot figure out which one.

• Are you working over $\Bbb Z/(2)$? – Pedro Tamaroff Nov 28 '13 at 22:46
• Hint: the result (or remainder) is a polynom of degree < 3 (the degree of modulus), of the form $R = x^3 - P \cdot (x^3+x+1)$, with some polynomial P. If you want the whole congruence class, it's $\{R + P \cdot (x^3+x+1) | P \in \mathbb{K}[x] \}$ where $\mathbb{K}$ is you base field. – Jean-Claude Arbaut Nov 28 '13 at 22:46
• @Pedro yes.. i didn't mentioned it, because i thought it wouldn't belong to the Task. So i think, i didn't understand Polynome congruences at all. – Toralf Westström Nov 28 '13 at 22:49
• At least you quickly understood that you didn't understand! Beginning of wisdom, according to Socrates. – hardmath Nov 28 '13 at 22:59

## 1 Answer

You're working over $\Bbb Z/(2)$. Note that $-1=1$ there, so from $x^3+x+1\equiv 0$ you get $x^3\equiv -x-1\equiv x+1$, that is, the class of $x^3$ is that of $1+x$.

• Allright. So lets try another example, to see if i understand correctly. Lets take for instance $x^4+x$. So i would get $x^4+x\equiv x-1 \equiv x+1$ .. right? – Toralf Westström Nov 28 '13 at 23:22
• @ToralfWestström $x^4\equiv xx^3\equiv x(x+1)\equiv x^2+x$. – Pedro Tamaroff Nov 28 '13 at 23:31
• Okay that makes sense for me. But it seems i am still not able to make my own calculations. So if have $x^3+x$ for example. It would be $x^3+x\equiv -1\equiv 1$ ? – Toralf Westström Nov 28 '13 at 23:56
• Yes, that is correct. – Pedro Tamaroff Nov 28 '13 at 23:59
• Downvote...? Was someone annoyed by $1=-1$? – Pedro Tamaroff Nov 29 '13 at 0:41