Finding the inverse of $x^3+x^2+1$ in $\Bbb F_2[x]/(x^4+x^2)$ with the Euclidean algorithm

Question

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?

Answer 1

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.

Answer 2

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!