In a previous question, I established that $x^5 + x^4 + 1$ is irreducible in $\mathbb{Z}_2[x]/(x^5 + x^4 + 1)$, so it will not be divisible by $x+1$. Hence $x^5+x^4+1$ will be coprime to $(x+1)^3 = x^3+x^2+x+1$
So far I have used the Euclidean algorithm to get:
$x^5+x^4+1 = (x^3+x^2+x+1)(x^2+1) + x$
$x^3+x^2+x+1 = (x^2+1)(x+1) + 0$
However, I know I have done something wrong - because the Euclidean algorithm should show that the gcd of $x^5+x^4+1$ and $x^3+x^2+x+1$ is $1$, not $(x^2+1)$.
On
Here's my approach to this one, which does not really depend too much on the standard theorems on polynomial rings--except for the Euclidean Algorithm--but does rely on a few simple observations about the polynomial
$p(x) = x^5 + x^4 + 1 = 0 \in \Bbb Z_2[x]/(x^5 + x^4 + 1) \tag{1}$
and a lot of grinding away at synthetic division. Very brutesy-forcey. I have adopted the notation
$p(x) = x^5 + x^4 + 1 \tag{2}$
because it allows to save typing and $\LaTeX$ all over the place. I will also,for similar reasons, use the shorthand
$R = \Bbb Z_2[x]/(p(x)). \tag{2}$
These things being said:.
We have
$p(x) = x^5 + x^4 + 1 = 0 \in R; \tag{3}$
this much is, I think, obvious. Now (3) implies
$x^5 + x^4 = 1 \in R, \tag{4}$
which follows from adding $1$ to each side of (3) and using the fact that $R$ is of characteristic $2$.
Then
$x^4(x + 1) = x^5 +x^4 = 1, \tag{5}$
which proves that $1 + x$ is in fact a unit in $R$ and that its inverse is $x^4$. We may now take the third power of each side of (5); we find
$x^{12}(1 + x)^3 = 1; \tag{6}$
from this we see that
$(1 + x)^{-3} = x^{12}. \tag{7}$
In a sense, we are now done. However, for the sake of good form if nothing else, the effort should be nade to reduce $(1 + x)^{-3}$ to a polynomial of degree less than $5$, since in principle $R$ need contain no powers of $x$ greater than $4$ by virtue of (3) and (4). We accomplish this reduction by computing the renainder of $x^{12}$ when divided by $p(x)$, via synthetic division. And here is where brute force comes into play. In what follows I shall recite the steps of the computation, presenting the quotient and remainder at each one, denoting the quotient by $q(x)$ and the remainder by $r(x)$:
1.) we divide $p(x)$ into $x^{12}$, and find
$q(x) = x^7, r(x) = x^{11} + x^7; \tag{13}$
2.) $p(x)$ into $r(x)$:
$q(x) = x^6, r(x) = x^{10} + x^7 + x^6; \tag{14}$
3.) $p(x)$ into $r(x)$:
$q(x) = x^5, r(x) = x^9 + x^7 + x^6 +x^5; \tag{15}$
4.) $p(x)$ into $r(x)$:
$q(x) = x^4, r(x) = x^8 + x^7 + x^6 +x^5 +x^4\tag{16}$
5.) $p(x)$ into $r(x)$:
$q(x) = x^3, r(x) = x^6 +x^5 +x^4 +x^3; \tag{17}$
6.) $p(x)$ into $r(x)$:
$q(x) = x, r(x) = x^4 +x^3 +x; \tag{18}$
since $\deg r(x) < 5$, we may stop at this point, in accord with the Euclidean Algorithm. According to these calculations, we then have
$(1 + x)^{-3} = x^4 +x^3 +x. \tag{19}$
We can in fact check (20) as follows:
$(x^4 + x^3 + x)(1 + x)^3 = (x^4 + x^3 + x)(1 + x)^2(1 + x); \tag{20}$
since
$(1 + x)^2 = 1 + x^2 \tag{21}$
in $R$, we have
$(x^4 + x^3 + x)(1 + x)^2 = (x^4 + x^3 + x)(1 + x^2) = x^6 + x^5 + x^4 + x; \tag{22}$
at last, we note that via (3)
$x^6 + x^5 + x^4 + x = x(x^5 + x^4 + 1) + x^4 = x^4, \tag{23}$
and thus
$(x^4 + x^3 + x)(1 + x)^3 = x^4(1 + x) = x^5 + x^4 = 1, \tag{24}$
validating our calculation of
$(1 + x)^{-3} = x^4 + x^3 + x \in R. \tag{25}$
Using the algorithm detailed in this answer with polynomials (and writing top to bottom instead of left to right),we get $$ \begin{array}{c|c|c|c} x^5+x^4+1&0&1&\\ x^3+x^2+x+1&1&0&\\ x&x^2+1&1&x^2+1\\ 1&\color{#C00}{x^4+x^3+x}&x^2+x+1&x^2+x+1\\ 0&x^5+x^4+1&x^3+x^2+x+1&x \end{array} $$ which says that in $\mathbb{Z}_2$, $$ (x^3+x^2+x+1)^{-1}=x^4+x^3+x\pmod{x^5+x^4+1} $$