I cannot find whether multiplicative inverse of $x^3+x^2+x+1 \pmod{x^5+x^4+x^3-x^2-x+1}$ over $\mathrm{GF}(3)$ exists. This problem must be solved with Extended Euclidean algorithm.
I tried to divide $x^5+x^4+x^3-x^2-x+1$ by $x^3+x^2+x+1$.
I think I divided it wrong. I got $x^2-2x-2$.
Thanks for any help
Best Answer
The problem you are trying to solve is not clearly stated, but what is clear is that you are having some difficulty with polynomial division, or (more likely) just think that you are. What probably happened is something that happens to everybody, a slip with signs.
We will do ordinary polynomial division. To start the division process, imitate school division. The polynomial $x^3+x^2+x+1$ "goes into" $x^5+x^4+x^3-x^2-x+1$ how many tines? Clearly $x^2$ times. So multiply $x^3+x^2+x+1$ by $x^2$, subtract from $x^5+x^4+x^3-x^2-x+1$. The raw remainder we get is $-2x^2-x+1$. Since we are working over the $3$ element field, this can be rewritten in various ways. It is sensible to replace the $-2$ by $1$, obtaining remainder $x^2-x+1$, or $x^2+2x+1$.
If negatives give you trouble, you could start by replacing $x^5+x^4+x^3-x^2-x+1$ by $x^5+x^4+x^3+2x^2+2x+1$.
Anyway, we have quotient $x^2$, remainder $x^2-x+1$. Continue the Euclidean algorithm process by dividing $x^3+x^2+x+1$ by $x^2-x+1$. You should get quotient $x+2$ (or $x-1$), remainder some version of $2x-1$. Continue.