# Find multiplicative inverse existense.

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

-
It sounds like the task really is to find whether the coset $x^3+x^2+x+1+I$ in the ring $GF(3)[x]/I$ has a multiplicative inverse or not. Here $I$ is the ideal generated by the polynomial $x^5+x^4+x^3-x^2-x+1$. – Jyrki Lahtonen May 27 '12 at 14:02
$$x^3+x^2+x+1 = x^2(x+1)+(x+1) = (x^2+1)(x+1)$$ while $$x^5+x^4+x^3-x^2-x+1 = x^4(x+1)+x^2(x+1)+x(x+1)+(x+1) = (x^4+x^2+x+1)(x+1)$$ and so the gcd is not a constant. Of course, this is not using the Extended Euclidean Algorithm as seems to be required, but I hope the results obtained by that method will be consistent with this observation. – Dilip Sarwate May 27 '12 at 14:27
If it's too much work / too error prone, then don't bother doing a complete division: you can make progress even if all you compute is the leading term of the quotient, which can be obtained by inspection. – Hurkyl May 27 '12 at 15:19

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.
@DonAntonio I thought the possibility of an inverse of a polynomial in the ring $\mathbb F_3[x]/(x^5+x^4+x^3-x^2-x+1)$ was under investigation, not an inverse over a field. – Dilip Sarwate May 27 '12 at 14:57