Finding inverse of polynomial in a field

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$.

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.

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$.