Finding the inverse of $x^3+x^2+1$ in $\Bbb F_2[x]/(x^4+x^2)$ with the Euclidean algorithm My first thought was successful: $x^4+x^2=x^2(x^2+1)$ and $x^3+x^2+1=x^2(x+1)+1$ so it is its own inverse because $(x^2(x+1)+1)^2\equiv x^4(x+1)^2+1\equiv x^4(x^2+1)+1\equiv1.$
The given solution claims to use the Euclidean algorithm, succintly, but I don't quite get it:

$x^4+x^2=(x^3+x^2+1)(x+1)+(x+1); \\ x^3+x^2+1=x^2(x+1)+1$
hence $1=(x^3+x^2+1)(x^3+x^2+1)+x^2(x^4+x^2)$

What is the logic in the above lines? How does it work in general?
 A: A possible way to "visualize" what happens, in analogy with the same algorithm for (the ring of) integers, is to (formally) use the formalism of continued fractions,
so let us write:
$$
\begin{aligned}
\frac{x^4+x^2}{x^3+x^2+1}
&=
(x+1)+\frac{x+1}{x^3+x^2+1}
\\
&=
(x+1)+\frac1{\frac{x^3+x^2+1}{x+1}}
\\
&=
(x+1)+\frac1{x^2+\frac1{x+1}}
\\
&=[\ x+1,\ x^2,\ x+1\ ]\text{ (in notation)}\ .
\end{aligned}
$$
Now we consider the "best approximation", which is $[\ x+1,\ x^2\ ]=x+1+\frac 1{x^2}$, and compute the difference:
$$
\begin{aligned}
&
\frac{x^4+x^2}{x^3+x^2+1}
-
\frac{x^3+x^2+1}{x^2}
\\
&\qquad
=
\frac
{x^2(x^4+x^2)-(x^3+x^2+1)^2}
{x^2(x^3+x^2+1)}
\\
&\qquad
=
\frac
{1}
{x^2(x^3+x^2+1)}
\\
\ .
\end{aligned}
$$
From the above computation we need only the last numerator computation,
$$
x^2(x^4+x^2)-(x^3+x^2+1)^2=1\ ,
$$
and on the R.H.S we have a constant polynomial... Exactly what we need!
A: For integers, if you're trying to find an inverse of $a$ mod $n$ using Euclidean algorithm, you would divide $n$ by $a$, find the remainder $r_1$, then divide $a$ by $r_1$, find the remainder $r_2$; divide $r_1$ by $r_2$, etc., until the remainder becomes 1. Here you're looking for the inverse of $x^3+x^2+1$ mod $x^4+x^2$, so you divide $x^4+x^2$ by $x^3+x^2+1$, find the remainder $x+1$, then divide $x^3+x^2+1$ by this remainder $x+1$, this time the remainder is already 1.
To find the inverse, you work backwards. The second equation tells you 
$$1 = (x^3+x^2+1) - (x^2(x+1))$$
By the first equation, 
$$x+1 = [x^4+x^2] - [(x^3+x^2+1)(x+1)]$$
Plug this into the above equation:
$$1=(x^3+x^2+1)- x^2(x^4+x^2-(x^3+x^2+1)(x+1)) \equiv (x^3+x^2+1)(1+x^3+x^2)$$
In short, you're doing exactly the same thing as when you solved congruence relations of integers using Euclidean algotithm.
