Finding inverse of polynomial in a field I'm having trouble with the procedure to find an inverse of a polynomial in a field. For example, take:


  In $\frac{\mathbb{Z}_3[x]}{m(x)}$, where $m(x) = x^3 + 2x +1$, find the inverse of $x^2 + 1$.


My understanding is that one needs to use the (Extended?) Euclidean Algorithm and Bezout's Identity. Here's what I currently have:

Proceeding with Euclid's algorithm:

$$ x^3 + 2x + 1  =(x^2 + 1)(x) + (x + 1) \\\\
  x^2 + 1 = (x + 1)(2 + x) + 2$$

We stop here because 2 is invertible in $\mathbb{Z}_3[x]$. We rewrite it using a congruence:

$$(x+1)(2+x) \equiv 2 \mod{(x^2+1)}$$

I don't understand the high level concepts sufficiently well and I'm lost from here. Thoughts?

Wikipedia has a page on this we a decent explanation, but it's still not clear in my mind.

Note that this question has almost the same title, but it's a level of abstraction higher. It doesn't help me, as I don't understand the basic concepts.

Thanks.
Write $f := x^3+2x+1$ and $g := x^2+1$. We want to find the inverse of $g$ in the field $\mathbb F_3[x]/(f)$ (I prefer to write $\mathbb F_3$ instead of $\mathbb Z_3$ to avoid confusion with the $3$-adic integers), i.e. we are looking for a polynomial $h$ such that $gh \equiv 1 \pmod f$, or equivalently $gh+kf=1$ for some $k\in \mathbb F_3[x]$. The Euclidean algorithm can be used to find $h$ and $k$:
\begin{align}
f &amp;= x\cdot g+(x+1)\\
g &amp;= (x+2)\cdot(x+1) + 2\\
(x+1) &amp;= (2x)\cdot2 + 1
\end{align}
Working backwards, we find
\begin{align}
1 &amp;= (x+1)-(2x)\cdot 2\\
&amp;= (x+1)-(2x)(g-(x+2)(x+1))\\
&amp;= (2x^2+x+1)(x+1)-(2x)g\\
&amp;= (2x^2+x+1)(f-xg)-(2x)g\\
&amp;= (2x^2+x+1)f- (x^3+2x^2)g\\
&amp;= (2x^2+x+1)f - (2x^3+x^2)g\\
&amp;= (2x^2+x+1)f + (x^3+2x^2)g.
\end{align}
So, the inverse of $g$ modulo $f$ is $h = x^3+2x^2 \pmod f = 2x^2+x+2 \pmod f$.
With the following identity, I would claim that the modular inverse of $(1 + x^2) \mod (1 + 2 x + x^3)$ is $1/2 (2 + x + x^2 + x^3)$, provided that $x$ is even.

$$1/2 (2 + x + x^2 + x^3) (1 + x^2) - 1/2 x (1 + x) (1 + 2 x + x^3) = 1$$

For example, if $x =20$, then
$1 + x^2 = 401$,
$1 + 2 x + x^3 = 8041$,
$1/2 (2 + x + x^2 + x^3) = 4211$,
and $(401)^(-1) mod 8041 = 4211$.