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.
$\endgroup$ 15 Answers
$\begingroup$$$ \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) $$
$\endgroup$ $\begingroup$$x^3 +6x+7 = (x+1)(x^2-x+7)$, and $x^2 + 3x + 2 = (x+1)(x+2)$, so the common factor is ...?
$\endgroup$ 3 $\begingroup$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$.
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$For $m(x) = π₯^3 + 6π₯ + 7$ and $n(x) = π₯^2 + 3π₯ + 2$,
Set
$m(x) = π₯^3 + 6π₯ + 7 = p(x)n(x) + r_1(x) = p(x)(π₯^2 + 3π₯ + 2) + r_1(x)$
Where $r_1(x)$ is your remainder term. You want to find some p(x) that multiplies with n(x) to give you the first term of m(x). You also want $deg r_1(x) < deg n(x)$. In this case, p(x) should be linear to get the $x^3$ term. So set $p(x) = ax+b$.
So now you have,
$m(x)= p(x)n(x) + r_1(x) = (ax+b)(π₯^2 + 3π₯ + 2) + r_1(x)$
Mulitply out:
$m(x) = (ax+b)(π₯^2 + 3π₯ + 2) + r_1(x) = ax^3 + (3a+b)x^2 + (2a+3b)x + 2b + r_1(x)$
Since the coefficient of $x^3$ in m(x) is 1, set $a = 1$. Similarly, set $3a+b=0$ since there's no $x^2$ term in m(x). Solve for b, $b = -3$.
Plug $a = 1$ and $b = -3$ into the rest of the polynomial:
$m(x) = x^3 -7x -6 + r_1(x)$
Then rearrange to find $r_1(x)$:
$r_1(x) = m(x) - p(x)n(x) = 13x + 13$
Now repeat the process!
This time set:
$n(x) = p_2(x)r_1(x) + r_2(x)$
Follow the same process to find $p_2(x)$ and $r_2(x)$, keep repeating this, eg once you know $r_2(x)$ the next equation would look like $r_1(x) = p_3(x)r_2(x) + r_3(x)$ etc, until you get a remainder term that equals zero. Then the previous remainder term is your gcd.
$\endgroup$
