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.

  • 1
    $\begingroup$ Are you working over $\Bbb Z/(2)$? $\endgroup$ – Pedro Tamaroff Nov 28 '13 at 22:46
  • $\begingroup$ 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. $\endgroup$ – Jean-Claude Arbaut Nov 28 '13 at 22:46
  • $\begingroup$ @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. $\endgroup$ – Toralf Westström Nov 28 '13 at 22:49
  • 1
    $\begingroup$ At least you quickly understood that you didn't understand! Beginning of wisdom, according to Socrates. $\endgroup$ – hardmath Nov 28 '13 at 22:59

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$.

  • $\begingroup$ 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? $\endgroup$ – Toralf Westström Nov 28 '13 at 23:22
  • 2
    $\begingroup$ @ToralfWestström $x^4\equiv xx^3\equiv x(x+1)\equiv x^2+x$. $\endgroup$ – Pedro Tamaroff Nov 28 '13 at 23:31
  • $\begingroup$ 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$ ? $\endgroup$ – Toralf Westström Nov 28 '13 at 23:56
  • 1
    $\begingroup$ Yes, that is correct. $\endgroup$ – Pedro Tamaroff Nov 28 '13 at 23:59
  • $\begingroup$ Downvote...? Was someone annoyed by $1=-1$? $\endgroup$ – Pedro Tamaroff Nov 29 '13 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.