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