Euclid's algorithm to find multiplicative inverses over a polynomial field 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?
 A: 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}$$
A: Let’s see. You divided $x^3+2x+1$ by $x+1$ to get a quotient of $x^2-x+3$ and a remainder of $-2$, right?
You’re finished right now, it seems to me: look at what you have:
$$
x^3+2x+1=(x+1)(x^2-x+3)\>-\>2\,,
$$
which I would immediately reinterpret as a congruence modulo $(x^3+2x+1$) as $(x+1)(x^2-x+3)\equiv2\pmod{(x^3+2x+1)}$, and then divide both sides by $2(x+1)$ to get $\frac1{x+1}\equiv(x^2-x+3)/2$.
Perhaps you were looking for something more complicated.
