0
$\begingroup$

I need to know the way to solve equations like this: $$(x^2+1)f(x) = 1 \pmod{x^3+1}$$ over a field $F_{3}[x]$.

Thanks in advance for any help.

$\endgroup$
  • 1
    $\begingroup$ Hint: as a start, observe that $x^3+1 = (x+1)^3$ in $\mathbb F_3[x]$. $\endgroup$ – Dilip Sarwate Nov 17 '13 at 14:45
  • 2
    $\begingroup$ Do you know how to apply the Euclidean algorithm? $\endgroup$ – Calvin Lin Nov 17 '13 at 14:56
  • 2
    $\begingroup$ Nitpick: $F_3[x]$ is not a field but a polynomial ring :-) $\endgroup$ – Jyrki Lahtonen Nov 17 '13 at 14:56
  • $\begingroup$ But to give you hint (I was away watching a fantastic darts match): Any residue class modulo $x^3+1$ has a unique representative of the form $a(x)=a_0+a_1x+a_2x^2$ with $a_0,a_1,a_2\in F_3$. Your task is to find the values of those constants in such a way that $a(x)(x^2+1)$ leaves remainder $1$ modulo $x^3+1$. You can brute force this either by testing all 27 combinations, or you can replace it with a linear system of three equations in the three unknowns, or you can use Calvin Lin's hint. $\endgroup$ – Jyrki Lahtonen Nov 17 '13 at 16:01
  • $\begingroup$ Thanks very much for your valuable hint Jyrki...It helped me a lot and I found the answer as : x^2+x+2. $\endgroup$ – Ali Nov 17 '13 at 19:24
0
$\begingroup$

Hint: Any residue class modulo $x^3+1$ has a unique representative of the form $a(x)=a_0+a_1x+a_2x^2$ with $a_0,a_1,a_2\in F_3$. Your task is to find the values of those constants in such a way that $a(x)(x^2+1)$ leaves remainder 1 modulo $x^3+1.$ You can brute force this either by testing all 27 combinations, or you can replace it with a linear system of three equations in the three unknowns, or you can use Calvin Lin's hint.

$\endgroup$
  • $\begingroup$ Moved the hint (that judging from OP's reaction) from comments to a CW-answer, as the OP didn't bite (yet). Will delete this, if the OP does give the details of how they eventually solved the problem. $\endgroup$ – Jyrki Lahtonen Nov 18 '13 at 5:53

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.