<s>[INST] Finding the inverse of $(x^2+2)$ in the field $S = \Bbb F_3[x]/(x^4+x^3+x^2+1)$ Let $S = \Bbb F_3[x]/(x^4+x^3+x^2+1)$.
Find the inverse of $(x^2+2)$ in $S$.
I know I'm looking for a polynomial $q(x)$ such that $(x^2+2)q(x) = 1 \mod x^4+x^3+x^2+1$
i.e $(x^2+2)q(x) + k(x)(x^4+x^3+x^2+1) = 1$ for some $k(x)$ in $\Bbb F_3[x]$
I'm not really sure how to find $q(x), k(x)$. I understand the Euclidean algorithm (in polynomials) needs to be applied, but I'm not really sure how to do this working over $\Bbb F_3[x]$.
 [/INST] In $\mathbb F_3[x]$, you could replace $x^2+2$ with $x^2-1$.
$$\color{purple}{x^4+x^3+x^2+1}=(\color{blue}{x^2-1})(x^2+x-1)+\color{green}x$$
$$\color{blue}{x^2-1}=x(\color{green}x)-\color{orange}1$$
So $$\color{orange}1=x[\color{green}x]-(\color{blue}{x^2-1})=x\left[\color{green}{x^4+x^3+x^2+1-( {x^2-1})(x^2+x-1)}\right]-(\color{blue}{x^2-1}) $$
$$=x(\color{purple}{x^4+x^3+x^2+1})\color{red}{-(x^3+x^2-x+1)}(x^2-1),$$
so an inverse of $x^2-1$ in $\mathbb F_3[x]/(\color{purple}{x^4+x^3+x^2+1})$
is $\color{red}{-(x^3+x^2-x+1)\equiv2x^3+2x^2+x+2}.$
</s>