<s>[INST] Finding modular inverse of $x^4$ in $GF(2^5)\mod (x^5+x^2+1)$ I cannot spot where I am going wrong in this. I am using Extended Euclidean's algorithm here.
$(x^5+x^2+1) = (x^4)(x) + (x^2+1)$
$(x^4) = (x^2+1)(x^2+1) + 1$
let $P(x)=x^4$ and $Q(x)=x^5+x^2+1$
$(x^5+x^2+1) + (x^4)(x) = (x^2+1)$
$(x^4) + (x^2+1)(x^2+1) = 1$
$P(x)+[Q(x)+P(x)(x)][Q(x)+P(x)(x)]=1$
$P(x)(1+xQ(x)+P(x)x^2+xQ(x)) +Q(x)(...)=1$
$P(x)(1+P(x)x^2)+Q(x)(...)=1$
$P(x)(1+x^6) + Q(x)(...)=1$
$(1+x^6) \bmod (x^5+x^2+1)=x^3+x+1$
I am getting the inverse of $x^4 \mod (x^5+x^2+1)$ as $x^3+x+1$ but it seems the right answer is $x^4+x^2+1$. Can anyone tell me where it is wrong?
 [/INST] We want to solve $$x^4 \cdot (c_0 + c_1 x + c_2 x^2 + c_3 x^4) = 1$$
multiplying this out gives
\begin{align}
& c_0 x^4 + c_1 x^5 + c_2 x^6 + c_3 x^8 \\
=&\, c_0 x^4 + c_1 (x^2 + 1) + c_2 (x^3 + x) + c_3 (x^3 + x^2) \\
=&\, c_1 + (c_1 + c_3) x^2 + (c_2 + c_3) x^3 + c_0 x^4 \\
\end{align}
so we want to solve the linear system:

*

*$c_1 = 1$

*$c_1 + c_3 = 0$

*$c_2 + c_3 = 0$

*$c_0 = 0$
to get our inverse $x + x^2 + x^3$
</s>