Euclidean Algorithm for polynomials

Question

I know how to use the extended euclidean algorithm for finding the GCD of integers but not polynomials. I can't really find any good explanations of it online. The question here is to find the GCD of m(x) = $\ x^3+6x+7 $ and n(x) = $\ x^2+3x+2 $.

I try to use it the same way as for integers but don't really get anywhere and just get huge lines without ever reducing it and getting closer to finding the GCD.

Answer 1

$x^3 +6x+7 = (x+1)(x^2-x+7)$, and $x^2 + 3x + 2 = (x+1)(x+2)$, so the common factor is ...?

Answer 2

First, we can write $m(x)$ as $n(x)$, times a quotient, plus a remainder:

$$m(x)=n(x)(x-3) + (13x+13)$$

Now, the $\gcd$ of $m(x)$ and $n(x)$ will be the same as the $\gcd$ of $n(x)$ with the remainder. In this case, the remainder divides $n(x)$:

$$n(x) = (13x+13)(\tfrac1{13}x+\tfrac2{13})$$

It makes sense at this point to move over a factor of $13$, leaving you with a nice $\gcd$.

Answer 3

Using, but not showing(!), the long division...

\begin{align} x^3+6x+7&=(x-3)(x^2+3x+2)+(13x+13)\\ x^2+3x+2&=\big(\frac{1}{13}x+\frac{2}{13}\big)(13x+13)+0 \end{align}

Shifting the 13's shows that $(x+1)$ is the greatest common divisor.

Answer 4

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

$$ \left( x^{2} + 3 x + 2 \right) $$

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