I did a huge amount of algebra and I think I ended up with the wrong answer. I got $(-x^4+3x^3-x^2-2x)$ which is obviously not the right answer.
So I started by saying I need $a(x)$ and $b(x)$ such that $a(x^4+x+1) + b(x^3 +x)=1$ and $b(x)$ will be the inverse. Then I tried to use the extended Euclidiean algorithm which took forever. I got:
$$x^4+x+1 = (x^3+x)(x) + (-x^2+x+1)$$
$$x^3+x = (-x^2+x+1)(-x-1) + (3x+1)$$
Then since $3x \equiv x \pmod 2$,
$$(-x^2+x+1) = (x+1)(-x+2) + (-1)$$
Since -1 = 1, I stopped there and got the gcd as 1. However when I did the extended version it did not seem to work. Where am I going wrong ?
The Euclidean Algorithm can be done using matrices:
$$\left[\begin{array}{cc|c}1&0&x^4 + x + 1\\0&1&x^3+x\end{array}\right]$$ Now take row 1 and add/subtract $x$ times row 2 from it: $$\left[\begin{array}{cc|c}1&x&x^2 + x + 1\\0&1&x^3+x\end{array}\right]$$ Now take row 2 and add/subtract $x+1$ times row 1 from it: $$\left[\begin{array}{cc|c}1&x&x^2 + x + 1\\x+1&x^2+x+1&x+1\end{array}\right]$$ Now take row 1 and add/subtract $x$ times row 2 from it: $$\left[\begin{array}{cc|c}x^2+x+1&x^3+x^2&1\\x+1&x^2+x+1&x+1\end{array}\right]$$ Now read off row 1 as an equation, giving the Bezout coefficients: $$(x^2+x+1)(x^4+x+1)+(x^3+x^2)(x^3+x)=1,$$ which implies that $(x^3+x)^{-1}\equiv(x^3+x^2)\pmod{x^4+x+1}$.
(Note that this also works for the gcd of two or more numbers; just make sure you're subtracting an integer times a row.)