How to verify the inverse of a polynomial in mod polynomial?

Question

This is in $F_2$. This might sound silly but I know that the inverse of $(x^3+x)$ in mod $(x^4+x+1)$ is $(x^3 + x^2)$ but I am not sure how to verify that. It should be that when I multiply $(x^3+x)$ by its inverse then I should get $1$. However,

$$(x^3+x)(x^3 + x^2) = x^6 + x^5 + x^4 + x^3$$

Now I don't know how that equals $1$ mod $(x^4+x+1)$.

Since $(x^4+x+1) = 0$, I can get that $x^4 = -1-x$ but what use is that :/

Answer 1

$x^6 + x^5 + x^4 + x^3 = x^2(x^4) + x(x^4) + x^4 + x^3 = x^2(x + 1) + x(x + 1) + (x + 1) + x^3$, using the $x^4 \equiv -1 -x \equiv 1 + x$ fact. (as we are in $F_2$, $-1 = 1$, etc.)

Now multiply out: $x^3 + x^2 + x^2 + x + x + 1 + x^3 = 1$, as all equals terms cancel ($a + a = 2a = 0a = 0$ as $2 \equiv 0$ in $F_2$).

Answer 2

The statement

$x^6+x^5+x^4+x^3$ equals $1$ modulo $x^4+x+1$

means that $x^6+x^5+x^4+x^3$ yields remainder $1$ when divided by $x^4+x+1$.

So, you should divide $x^6+x^5+x^4+x^3$ by $x^4+x+1$ and check if the remainder is $1$.

Answer 3

We have $$ (x^4+x+1)(x^2+x+1)=x^6+x^5+x^4+x^3+2x^2+2x+1\equiv (x^6+x^5+x^4+x^3)+1\bmod 2 $$ You can find the factor $x^2+x+1$ by the ansatz $x^2+ax+b$ and then determine $a$ and $b$.

Answer 4

$x^6 + x^5 + x^4 + x^3$ reduces to $1$ because that is the remainder after dividing by $x^4+x+1$.