1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Learning the Euclidean Algorithm to solve this is probably faster and easier than any other method. $\endgroup$ – Jonathan Mar 6 '18 at 16:55
  • $\begingroup$ So if, for example in: $a(x)(p)+b(x)(q)=gcd(p,q)$, $a=1$, and $b=1$? Is that how you want to do it? $\endgroup$ – user535339 Mar 6 '18 at 16:56
2
$\begingroup$

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) $$

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

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.