I have two polynomials:
$$f(x)=x^5+x^3+x+1\\ g(x)=x^4+x^3+x+1.$$
I have to find out $\gcd(f,g)$ over $\operatorname{GF}(2).$
I think the gcd is: $x+1.$ But I am not sure, because here is the remainder $x^2+1.$
Another problem is to find out polynomials $a(x)$ and $b(x),$ like $$\gcd(f(x),g(x))= a(x)f(x)+b(x)g(x).$$ Maybe I can use Extended Euclid's algorithm, but I have no idea how to do it.
On
It's easy: $\,(f,g) = (f\!-\!g,g) = (\color{#c00}x^4(x\!-\!1),g)=\bbox[5px,border:1px solid #0a0]{x\!-\!1}\,$ by $\,\color{#c00}x\nmid g;\,\ x\!-\!1\mid g\,$ by $\,g(1)=0$
For part two, to find the gcd Bezout identity it suffices to solve
$$\begin{align} c\, (f-g)\ +\ b\, g &\,=\, x\!+\!1\,\ (=x\!-\!1)\\[.2em] \iff\ c x^4(x\!+\!1) + b (1\!+\!x^3) (x\!+\!1) &\,=\, x\!+\!1\\[.2em] \iff\ c\, x^4 + b\, (1\!+\!x^3) &\,=\, 1\ \ {\rm via\ cancel}\,\ x\!+\!1\end{align}$$
By inspection an obvious choice is $\, b = 1\!-\!x^3,\ c =\color{#0a0}{x^2}.\,$ Or, by Gauss's algorithm
$\bmod\, \color{#c00}{1+x^3}\!:\ \ c\equiv \dfrac{1}{x(\color{#c00}{x^3})}\equiv \dfrac{1}{x(\color{#c00}{-1})}\equiv \dfrac{x^2}{-\color{#c00}{x^3}}\equiv \dfrac{\color{#0a0}{x^2}}{\color{#c00}1}$
If you wish to mechanically apply the extended Euclidean algorithm (vs. above optimizations thereof) then it is most convenient to use the forward form described here. The vulgar backward form is far more cumbersome and error prone.
Note that$$x^5+x^3+x+1=(x^4+x^3+x+1)(x+1)+x^2+x,$$that$$x^4+x^3+x+1=(x^2+x)x^2+x+1,\tag1$$and that$$x^2+1=(x+1)x.$$The remainder of this final polynomial division is $0$ and therefore$$\gcd(x^5+x^3+x+1,x^4+x^3+x+1)=x+1$$since $x+1$ is the remainder of the division $(1)$ (that is, it is the last non-null remainder).