I'm trying to find the multiplicative inverse of $\overline{x+1}$ over the field $\mathbb{F}_3[x]/(x^3 + 2x + 1)$. I know I need to use Euclid's algorithm to do so, but I keep running into some difficulties.
I let $f(x) = x^3 + 2x + 1$ and $g(x) = x+1$. Then I should be able to compute
$$f(x) = q_1(x)g(x) + r_1(x)$$
$$g(x) = q_2(x)r_1(x) + r_2(x)$$
$$\vdots$$
$$ r_{m-1}(x) = q_{m+2}(x)r_m(x)$$ and then back substitute through the algorithm to solve for $a(x), b(x)$ in
$$ a(x)g(x) + b(x)f(x) = 1.$$ My problem is likely elementary, but it has me confused: I cannot find $q_1$, $q_2$ to make what should probably be a rather trivial iteration of the algorithm work at all. If I was solving for, say, the multiplicative inverse of $\overline{x ^2}$, I could let $f(x) = (x)(x^2) + (2x+1)$ with $g(x) = x^2 = (2x+1)(2x+2)+1$. The division follows nicely from there. However, I can't find out where I'm going wrong for $\overline{x+1}$... What am I missing?
You could use polynomial long division, which as discussed & shown in the linked Wikipedia article is done similarly to base $10$ long division except rather than using powers of $10$, you use powers of $x$ instead. Also, similar to what the long division method does, you can notice by adding & subtracting various terms and regrouping them that
$$\begin{equation}\begin{aligned} x^3 + 2x + 1 & = x^3 + (x^2 - x^2) + (- x + x) + 2x + (3 - 3) + 1 \\ & = (x^3 + x^2) - (x^2 + x) + (3x + 3) - 2 \\ & = x^2(x + 1) - x(x + 1) + 3(x + 1) - 2 \\ & = (x^2 - x + 3)(x + 1) - 2 \end{aligned}\end{equation}\tag{1}\label{eq1A}$$
You thus have
$$q_1(x) = x^2 - x + 3 \tag{2}\label{eq2A}$$
$$r_1(x) = -2 \tag{3}\label{eq3A}$$
Also, note a fast way to determine $r_1(x)$ is to use that
$$x + 1 \equiv 0 \pmod{x + 1} \implies x \equiv -1 \pmod{x + 1} \tag{4}\label{eq4A}$$
Thus, this means
$$x^3 + 2x + 1 \equiv (-1)^3 + 2(-1) + 1 \equiv -2 \pmod{x + 1} \tag{5}\label{eq5A}$$