Find the GCD of a polynomial using the extended Euclidean algorithm and express it in the form $a(x)f(x)+b(x)g(x)$

Question

I am working on a problem that I can not seem to finish.

Find the gcd of $f(x)=x^7+1$ and $g(x)=x^6+x^5+x^3+1$, and express it in the form $a(x)f(x)+b(x)g(x)$ using the extended euclidean algorithm.

I have performed the extended euclidean algorithm to find the following $$f(x)=(x-1)g(x)+(x^5-x^4+x^3-x+2)$$ $$g(x)=(x+2)(x^5-x^4+x^3-x+2)+(x^4-x^3+x^2-3)$$ $$x^5-x^4+x^3-x+2=(x)(x^4-x^3+x^2-3)+(2x+2)$$ $$x^4-x^3+x^2-3=(\frac{1}{2}x^3-x^2+\frac{3}{2}x-\frac{3}{2})(2x+2)+0$$ This should give us the GCD as following $$\gcd(f,g)=\gcd(x^5-x^4+x^3-x+2, 2x+2)=2x+2$$ And the monic GCD then becomes $$\gcd(f,g)=x+1$$

This is where I get stuck. Now that I have this I am not sure how to algebraically get back to the form $a(x)f(x)+b(x)g(x)$

The answer as provided in the solutions is $$\gcd(f(x),g(x))=x^4+x^3+x^2+1=xf(x)+(x^2+x+1)g(x)$$

I do not understand how to proceed and get to the answer. I have tried going backward but I am not getting anywhere. How do I go from $x+1$ to the correct solution?

Answer 1

With some guessing, I figured out that the original question asks the $\gcd$ of these two polynomials over $\Bbb F_2$.

This means that $f, g$ are viewed as polynomials in $\Bbb F_2[x]$. Therefore the algorithm stops at the step $x^5-x^4+x^3-x+2=(x)(x^4-x^3+x^2-3)+(2x+2)$, as the remainder is now $0$.

Answer 2

Here is how the extended Euclidean algorithm works in this case (over $\mathbf F_2$). Keep in mind that, in characteristic $2$, adding or subtracting is the same.

This extended algorithm is based on the remark that all remainders are linear combination of the two given polynomials, and the coefficients thereof are computed recursively. \begin{array}{rccl} r_n &u_n&v_n & q_n\\\hline f(x) & 0 & 1 \\ g(x) & 1 & 0 & x+1 \\ \hline x^5+x^4+x^3 + x & x+1 & 1 & x \\ x^4+x^3 + x^2 + 1 & 1+x(x+1) & x & x \\[-0.5ex] &=\color{red}{x^2+x+1} & \color{red}x \\ \hline 0 \end{array}

Answer 3

There is an interesting way to find the solutions for "Bezout's equation" $ax+by=mdc(a,b)$ using continued fractions. For instance, for numbers: find $(x,y) \in \mathbb Z^2$ s.t. $11x + 7y = 1$. The continued fraction of $11/7$ is $[1;1,1,3]$. By removing the last digit, $[1;1,1] = 3/2$, we see that $11 \cdot 2 + 7 \cdot (-3) = 1$, therefore $(x,y) = (2,-3)$ satisfy the equation $11x + 7y = 1$. The thing is: the algorithm is exactly the same for polynomials!

Answer 4

$$ \left( x^{7} + 1 \right) $$

$$ \left( x^{6} + x^{5} + x^{3} + 1 \right) $$

$$ \left( x^{7} + 1 \right) = \left( x^{6} + x^{5} + x^{3} + 1 \right) \cdot \color{magenta}{ \left( x - 1 \right) } + \left( x^{5} - x^{4} + x^{3} - x + 2 \right) $$ $$ \left( x^{6} + x^{5} + x^{3} + 1 \right) = \left( x^{5} - x^{4} + x^{3} - x + 2 \right) \cdot \color{magenta}{ \left( x + 2 \right) } + \left( x^{4} - x^{3} + x^{2} - 3 \right) $$ $$ \left( x^{5} - x^{4} + x^{3} - x + 2 \right) = \left( x^{4} - x^{3} + x^{2} - 3 \right) \cdot \color{magenta}{ \left( x \right) } + \left( 2 x + 2 \right) $$ $$ \left( x^{4} - x^{3} + x^{2} - 3 \right) = \left( 2 x + 2 \right) \cdot \color{magenta}{ \left( \frac{ x^{3} - 2 x^{2} + 3 x - 3 }{ 2 } \right) } + \left( 0 \right) $$ $$ \frac{ 0}{1} $$ $$ \frac{ 1}{0} $$ $$ \color{magenta}{ \left( x - 1 \right) } \Longrightarrow \Longrightarrow \frac{ \left( x - 1 \right) }{ \left( 1 \right) } $$ $$ \color{magenta}{ \left( x + 2 \right) } \Longrightarrow \Longrightarrow \frac{ \left( x^{2} + x - 1 \right) }{ \left( x + 2 \right) } $$ $$ \color{magenta}{ \left( x \right) } \Longrightarrow \Longrightarrow \frac{ \left( x^{3} + x^{2} - 1 \right) }{ \left( x^{2} + 2 x + 1 \right) } $$ $$ \color{magenta}{ \left( \frac{ x^{3} - 2 x^{2} + 3 x - 3 }{ 2 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ x^{6} - x^{5} + x^{4} - x^{3} + x^{2} - x + 1 }{ 2 } \right) }{ \left( \frac{ x^{5} + x^{2} - x + 1 }{ 2 } \right) } $$ $$ \left( x^{6} - x^{5} + x^{4} - x^{3} + x^{2} - x + 1 \right) \left( \frac{ x^{2} + 2 x + 1 }{ 2 } \right) - \left( x^{5} + x^{2} - x + 1 \right) \left( \frac{ x^{3} + x^{2} - 1 }{ 2 } \right) = \left( 1 \right) $$ $$ \left( x^{7} + 1 \right) = \left( x^{6} - x^{5} + x^{4} - x^{3} + x^{2} - x + 1 \right) \cdot \color{magenta}{ \left( x + 1 \right) } + \left( 0 \right) $$ $$ \left( x^{6} + x^{5} + x^{3} + 1 \right) = \left( x^{5} + x^{2} - x + 1 \right) \cdot \color{magenta}{ \left( x + 1 \right) } + \left( 0 \right) $$ $$ \mbox{GCD} = \color{magenta}{ \left( x + 1 \right) } $$ $$ \left( x^{7} + 1 \right) \left( \frac{ x^{2} + 2 x + 1 }{ 2 } \right) - \left( x^{6} + x^{5} + x^{3} + 1 \right) \left( \frac{ x^{3} + x^{2} - 1 }{ 2 } \right) = \left( x + 1 \right) $$

.......