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.
 A: This is very easy when using the augmented-matrix form of the extended Euclidean algorithm, i.e. we perform the Euclidean algorthm while keeping track of each remainders expression as a linear combination of $f$ and $g$ as follows.
$\begin{eqnarray}
(1)&&  &&f = x^3\!+2x+1 &\!\!=&\, \left<\,\color{#c00}1,\,\color{#0a0}0\,\right>\quad\ \ \, {\rm i.e.}\ \qquad f\, =\ \color{#c00}1\cdot f\, +\, \color{#0a0}0\cdot g\\
(2)&&  &&\qquad\ \,  g =x^2\!+1 &\!\!=&\, \left<\,\color{#c00}0,\,\color{#0a0}1\,\right>\quad\ \ \,{\rm i.e.}\ \qquad g\, =\ \color{#c00}0\cdot f\, +\, \color{#0a0}1\cdot g\\
(3)&=&(1)-x(2)\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\ \ x+1 \,&\!\!=&\, \left<\,\color{#c00}1,\,\color{#0a0}{-x}\,\right>\ \ \ {\rm i.e.}\quad x\!+\!1\, =\, \color{#c00}1\cdot f\,\color{#0c0}{-\,x}\cdot g\\
(4)&=&(2)+(1\!-\!x)(3)\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\qquad\ 2 \,&\!\!=&\, \left<\,\color{#c00}{1\!-\!x},\,\color{#0a0}{1\!-\!x+x^2}\,\right>\\
\end{eqnarray}$
Hence the prior line implies: $\,\ 2\, =\, (\color{#c00}{1\!-\!x})f + (\color{#0a0}{1\!-\!x\!+\!x^2})g,\, $ so reducing this mod $f$ and $3$
we get in $\,\Bbb Z_3[x] \bmod f\!:\,\  {-}1\equiv 2 \equiv (\color{#0a0}{1\!-\!x\!+\!x^2})g\ \Rightarrow\ \bbox[6px,border:1px solid red]{g^{-1}\equiv\, {-}(\color{#0a0}{1\!-\!x\!+\!x^2})}$
Remark $\ $  Generally, this method is easier to memorize and much less error-prone than the alternative "back-substitution" method.
This is a special-case of  Hermite/Smith row/column reduction of matrices to triangular/diagonal normal form, using the division/Euclidean algorithm to reduce entries modulo pivots. Though one can understand this knowing only the analogous linear algebra elimination techniques, it will become clearer when one studies modules - which, informally, generalize vector spaces by allowing coefficients from rings vs. fields. In particular, these results are studied when one studies normal forms for finitely-generated modules over a PID, e.g. when one studies linear systems of equations with coefficients in the non-field! polynomial ring $\rm F[x],$ for $\rm F$ a field, as above.
A: Another way to do this, is by representing the elements of your quotient field (which is a three-dimensional vector space with base field GF(3)) as matrices with respect to the basis 1, x, x^2. Multiplication by x sends 1 to x, x to x^2 and x^2 to x^3 = -2x - 1 = x + 2 (modulo 3). So (multiplication by) x is represented by the following matrix m:
\begin{pmatrix}
    0 & 0 & 2 \\
    1 & 0 & 1  \\
    0 & 1 & 0 
\end{pmatrix}
m^0 (corresponding to multiplication by x^0 = 1) is the identity matrix:
\begin{pmatrix}
    1 & 0 & 0 \\
    0 & 1 & 0  \\
    0 & 0 & 1 
\end{pmatrix}
and m^2 (multiplication by x^2) equals:
\begin{pmatrix}
    0 & 2 & 0 \\
    0 & 1 & 2  \\
    1 & 0 & 1 
\end{pmatrix}
The element (x^2 + 1)^-1 is represented by (m^2 + m^0)^-1, which equals
\begin{pmatrix}
    2 & 1 & 2 \\
    1 & 1 & 2  \\
    2 & 1 & 1 
\end{pmatrix}
The coefficients of (x^2 + 1)^-1 can be read off from the first column of this matrix: (m^2 + m^0)^-1 = 2m^0 + m + 2m^2, so (x^2 + 1)^-1 = 2 + x + 2x^2. Summarizing: your problem can be solved by adding, multiplying and inverting matrices.
A: The Euclidean algorithm begins with two polynomials $r^{(0)}(x)$ and $r^{(1)}(x)$ such that $\deg r^{(0)}(x) > \deg r^{(1)}(x)$ and then iteratively finds 
quotient polynomials $q^{(1)}(x), q^{(2)}(x), \ldots$ and remainder polynomials
$r^{(2)}(x), r^{(3)}(x), \ldots $ of successively smaller degrees 
via division
$$\begin{align*}
r^{(0)}(x) &= q^{(1)}(x)\cdot r^{(1)}(x) + r^{(2)}(x)\\
r^{(1)}(x) &= q^{(2)}(x)\cdot r^{(2)}(x) + r^{(3)}(x)\\
\vdots\qquad &= \qquad\qquad\vdots
\end{align*}$$
One version of the Extended Euclidean Algorithm also finds pairs of polynomials
$(s^{(0)}(x),t^{(0)}(x)),  (s^{(1)}(x),t^{(1)}(x)), 
(s^{(2)}(x),t^{(2)}(x)) \ldots$ where $(s^{(0)}(x),t^{(0)}(x)) = (1,0)$
and $(s^{(1)}(x),t^{(1)}(x)) = (0,1)$ that satisfy the generalized
Bezout identity
$$s^{(i)}(x)\cdot r^{(0)}(x) + t^{(i)}(x)\cdot r^{(1)}(x)
= r^{(i)}(x).$$
These polynomials satisfy the "same" recursion as the remainder polynomials,
 viz.,
$$\begin{align*}
r^{(i+1)}(x) &= r^{(i-1)}(x) - q^{(i)}(x)\cdot r^{(i)}(x)\\
s^{(i+1)}(x) &= s^{(i-1)}(x) - q^{(i)}(x)\cdot s^{(i)}(x)\\
t^{(i+1)}(x) &= t^{(i-1)}(x) - q^{(i)}(x)\cdot t^{(i)}(x)\\
\end{align*}$$
This form of the extended Euclidean algorithm is useful in 
practical applications since only two polynomials $r, s,$ and
$t$ need to be remembered with each new $(i+1)$-th polynomial
replacing the $(i-1)$-th polynomial which is no longer needed.
In your instance, you have $r^{(0)}(x) = x^3 + 2x+1$ and
$r^{(1)}(x) = x^2 + 1$.  You have already computed the quotient
and remainder sequence ending with $r^{(3)}(x) = 2$. Now compute
$t^{(2)}(x)$ and $t^{(3)}(x)$ iteratively using the sequence
of quotient polynomials and write
$$\begin{align*}
s^{(3)}(x)\cdot (x^3 + 2x + 1) + t^{(3)}(x)\cdot(x^2 + 1) &= 2\\
-s^{(3)}(x)\cdot (x^3 + 2x + 1) - t^{(3)}(x)\cdot(x^2 + 1) &= 1\\
(-t^{(3)}(x))\cdot (x^2 + 1) &= 1 ~ \mod (x^3 + 2x + 1)
\end{align*}$$
and deduce that the multiplicative inverse of $x^2 + 1$ in
$\mathbb Z_3[x]/(x^3 + 2x + 1)$ is $-t^{(3)}(x)$.  Note that
the $s^{(i)}(x)$ sequence does not need to be computed at all
if all that one needs is the inverse. 
A: The same algorithm used to solve the linear diophantine equation can be used here.
$$
\begin{array}{c}
&&x&x-1&(x+1)/2\\
\hline
1&0&1&1-x&(x^2+1)/2\\
0&1&-x&x^2-x+1&-(x^3+2x+1)/2\\
x^3+2x+1&x^2+1&x+1&2&0
\end{array}
$$
Thus,
$$
(1-x)(x^3+2x+1)+(x^2-x+1)(x^2+1)=2
$$
Thus, the inverse of $x^2+1$ is $\tfrac12(x^2-x+1)$ mod $x^3+2x+1$.
A: 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 &= x\cdot g+(x+1)\\
g &= (x+2)\cdot(x+1) + 2\\
(x+1) &= (2x)\cdot2 + 1
\end{align}
Working backwards, we find
\begin{align}
1 &= (x+1)-(2x)\cdot 2\\
&= (x+1)-(2x)(g-(x+2)(x+1))\\
&= (2x^2+x+1)(x+1)-(2x)g\\
&= (2x^2+x+1)(f-xg)-(2x)g\\
&= (2x^2+x+1)f- (x^3+2x^2)g\\
&= (2x^2+x+1)f - (2x^3+x^2)g\\
&= (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$.
A: 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$.
