Greatest Common Divisor of two Polynomials.

Question

Find the $\gcd(x^3-6x^2+14x-15, x^3-8x^2+21x-18)$ over $\mathbb{Q}[x]$. Then find two polynomials $a(x),b(x) \in \mathbb{Q}[x]$ such that, $$a(x)(x^3-6x^2+14x-15) + b(x)(x^3-8x^2+21x-18)=\gcd(x^3-6x^2+14x-15, x^3-8x^2+21x-18)$$

I have managed to find, $$x^3-6x^2+14x-15=(x-3)(x^2-3x+5)$$ $$x^3-8x^2+21x-18=(x-3)(x-3)(x-2)$$

Now since $x^2-3x+5$ is irreducible over $\mathbb{Q}[x]$ and so the greatest common divisor is $(x-3)$. Now to find $a(x)$ and $b(x)$ I have no clue how to do that. I have looked online and it seems there is extended euclidean algorithm for polynomials but I haven't formally learned it in my class yet, so I was wondering if there is another efficient way to find these polynomials. Any help is appreciated, thanks!

Answer 1

This is just the Extended Euclidean Algorithm. Instead of back-substitution, I have always preferred to write the construction steps in the style of continued fractions. Furthermore, I have always depended on the kindness of strangers.

$$ \left( x^{3} - 6 x^{2} + 14 x - 15 \right) $$

$$ \left( x^{3} - 8 x^{2} + 21 x - 18 \right) $$

$$ \left( x^{3} - 6 x^{2} + 14 x - 15 \right) = \left( x^{3} - 8 x^{2} + 21 x - 18 \right) \cdot \color{magenta}{ \left( 1 \right) } + \left( 2 x^{2} - 7 x + 3 \right) $$ $$ \left( x^{3} - 8 x^{2} + 21 x - 18 \right) = \left( 2 x^{2} - 7 x + 3 \right) \cdot \color{magenta}{ \left( \frac{ 2 x - 9 }{ 4 } \right) } + \left( \frac{ 15 x - 45 }{ 4 } \right) $$ $$ \left( 2 x^{2} - 7 x + 3 \right) = \left( \frac{ 15 x - 45 }{ 4 } \right) \cdot \color{magenta}{ \left( \frac{ 8 x - 4 }{ 15 } \right) } + \left( 0 \right) $$ $$ \frac{ 0}{1} $$ $$ \frac{ 1}{0} $$ $$ \color{magenta}{ \left( 1 \right) } \Longrightarrow \Longrightarrow \frac{ \left( 1 \right) }{ \left( 1 \right) } $$ $$ \color{magenta}{ \left( \frac{ 2 x - 9 }{ 4 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 2 x - 5 }{ 4 } \right) }{ \left( \frac{ 2 x - 9 }{ 4 } \right) } $$ $$ \color{magenta}{ \left( \frac{ 8 x - 4 }{ 15 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 4 x^{2} - 12 x + 20 }{ 15 } \right) }{ \left( \frac{ 4 x^{2} - 20 x + 24 }{ 15 } \right) } $$ $$ \left( x^{2} - 3 x + 5 \right) \left( \frac{ 2 x - 9 }{ 15 } \right) - \left( x^{2} - 5 x + 6 \right) \left( \frac{ 2 x - 5 }{ 15 } \right) = \left( -1 \right) $$ $$ \left( x^{3} - 6 x^{2} + 14 x - 15 \right) = \left( x^{2} - 3 x + 5 \right) \cdot \color{magenta}{ \left( x - 3 \right) } + \left( 0 \right) $$ $$ \left( x^{3} - 8 x^{2} + 21 x - 18 \right) = \left( x^{2} - 5 x + 6 \right) \cdot \color{magenta}{ \left( x - 3 \right) } + \left( 0 \right) $$ $$ \mbox{GCD} = \color{magenta}{ \left( x - 3 \right) } $$ $$ \left( x^{3} - 6 x^{2} + 14 x - 15 \right) \left( \frac{ 2 x - 9 }{ 15 } \right) - \left( x^{3} - 8 x^{2} + 21 x - 18 \right) \left( \frac{ 2 x - 5 }{ 15 } \right) = \left( - x + 3 \right) $$

............

Answer 2

If I interpreted your question correctly and you want to do something like this, where in:

$a(x)(p)+b(x)(q)=gcd(p,q)$, $a=1$, and $b=1$

You can restate your expression as:

$$a(x)(x-3)(x^2-3x+5)+b(x)(x-3)(x-3)(x-2)$$ $$(x-3)\left(a(x)(x^2-3x+5)+b(x)(x-3)(x-2)\right)$$

Since this has to equal the $gcd$, which is $x-3$:

$$(x-3)\left(a(x)(x^2-3x+5)+b(x)(x-3)(x-2)\right)=x-3$$

$$\left(a(x)(x^2-3x+5)+b(x)(x-3)(x-2)\right)=1$$

Note: There are infinitely many solutions for $a(x)$ and $b(x)$ (but might not satisfy the definition of polynomials), since $0\le a(x)\le 1$ and $0\le b(x)\le 1$

Here, $a(x)(x^2-3x+5)$ and $b(x)(x-3)(x-2)$ sum up to $1$, so one instance is that they can individually sum up to $\dfrac 12$, since $\dfrac 12+\dfrac 12=1$.

So:

$$a(x)(x^2-3x+5)=\dfrac 12$$

$$b(x)(x-3)(x-2)=\dfrac 12$$

Can you figure this out?

Answer 3

You have the complete extended Euclid algorithm (which IMHO is the best way) given already in Will Jaggy's post.

Given that you already extracted $x-3$ as GCD, here is a perhaps quicker way (which may not generalise much). We simplify a bit by noting we seek linear $a(x), b(x)$, s.t.:

$a(x)\color{blue}{(x^2-3x+5)} + b(x) \color{blue}{(x-3)(x-2)}=1$. Setting $x=2, 3$ we get $a(x) = \frac1{15}(-2x+9)$.

Thus we are left with $\tfrac1{15}(-2x+9)\color{blue}{(x^2-3x+5)} + (px+q)\color{blue}{ (x-3)(x-2)}=1$
Comparing coeffs of the cubic term and the constant, $\implies p=\frac2{15},\; 3+6q = 1\implies q = -\frac13$.
So $$\tfrac1{15}(-2x+9)\color{blue}{(x^2-3x+5)} + \tfrac1{15}(2x-5)\color{blue}{(x-3)(x-2)}=1$$

Multiply this by $\color{blue}{x-3}$ if you want to see the equation in form $a(x) p_1(x) + b(x) p_2(x) = \gcd(p_1, p_2)$.