Im working out a problem where I find out the GCD of two polynomials using Euclid's Algorithm, and then I need to use Bezout's Identity to make
$\gcd(r,s)=ra+sb$
The question gives me
$x^5+1$ and $x^3+1$ in $F_2[x]$. Using Euclid's Alg. I get
$x^5+1=(x^3+1)x^2+(x^2+1)$
$x^3+1=(x^2+1)x+(x+1)$
$x^2+1=(x+1)(x+1)+0$
So the GCD is $x+1$.
Then, by Bezout's Identity,
(1) $x+1=(x^3+1)+(x^2+1)(x)$
(2) $x+1=(x^3+1)+((x^5+1)+(x^3+1)(x^2))(x)$
This next step is where I am confused. The book gives me
(3) $x+1=(x^5+1)(x)+(x^3+1)(x^3+1)$
However, if I multiply out (2), I get the following:
$x+1=(x^3+1)+(x^5+1)(x)+(x^3+1)(x^2)(x)$
$x+1=(x^3+1)+(x^5+1)(x)+(x^3+1)(x^3)$
So, how does (2) simplify to (3)?
Best Answer
The arithmetic has been explained. I explain how to eliminate such hairy error-prone arithmetic by replacing the painful back-substitution with simpler forward-computation of the Bezout identity using row-operations. Using the verson of the Extended Euclidean Algorithm described here yields
$$\begin{array}{rrr} x^5+1 & 1 & 0\\ x^3+1 & 0 & 1\\ x^2+1 & 1 & x^2\\ x+1 & \color{#c00}x & \color{#0a0}{x^3+1}\\ 0 & \ldots & \ldots \end{array}$$
where above lines $\,\ a\ \ b\ \ c\ \,$ mean $\ a = b(x^5+1) + c(x^3+1).\ $ So the Bezout identity is
$$ x+1 \,=\, \color{#c00}{x}(x^5+1)+ (\color{#0a0}{x^3+1})(x^3+1)\quad $$
The linked post describes the algorithm in great detail, in a way that is easy to remember.
Here is another example computing $\rm\ gcd(141,19),\,$ with the equations written explicitly
$$\rm\begin{eqnarray}(1)\quad \color{#C00}{141}\!\ &=&\,\ \ \ 1&\cdot& 141\, +\ 0&\cdot& 19 \\ (2)\quad\ \color{#C00}{19}\ &=&\,\ \ \ 0&\cdot& 141\, +\ 1&\cdot& 19 \\ \color{#940}{(1)-7\,(2)}\, \rightarrow\, (3)\quad\ \ \ \color{#C00}{ 8}\ &=&\,\ \ \ 1&\cdot& 141\, -\ 7&\cdot& 19 \\ \color{#940}{(2)-2\,(3)}\,\rightarrow\,(4)\quad\ \ \ \color{#C00}{3}\ &=&\, {-}2&\cdot& 141\, + 15&\cdot& 19 \\ \color{#940}{(3)-3\,(4)}\,\rightarrow\,(5)\quad \color{#C00}{{-}1}\ &=&\,\ \ \ 7&\cdot& 141\, -\color{#0A0}{ 52}&\cdot& \color{#0A0}{19} \end{eqnarray}\qquad$$