# Highest common factor, Polynomial division

• Jan 21st 2010, 12:35 PM
craig
Highest common factor, Polynomial division
Hi, think this is the correct forum, apologies if not.

Find the highest common factor of the polynomials
$x^5 - 2x^4 - 3x^3 + 13x^2 -16x + 6$ and $x^4 - 2x^3 - 2x^2 + 8x - 8$.

Hence factorise $x^4 - 2x^3 - 2x^2 + 8x - 8$ into irreducible polynomials in $R[x]$.

First I started off by factorising, by long division I got the following:

$x^5 - 2x^4 - 3x^3 + 13x^2 -16x + 6 = x(x^4 - 2x^3 - 2x^2 + 8x - 8) + (-x^3 +5x^2-8x+6)$

Not sure where to go from here. I'm ok with the Euclidean algorithm but not sure how to apply it here?

• Jan 21st 2010, 01:27 PM
craig
Edit just seen that I've not fully completed the algorithm yet! Think I can manage this..
• Jan 22nd 2010, 05:26 AM
HallsofIvy
I wondered about that- because what you wrote involved neither factoring nor long division!
• Jan 22nd 2010, 08:26 AM
craig
Yeh sorry about that. Posted the question and then realised that I'd only done the first bit... oops.
• Jan 22nd 2010, 09:03 AM
Dinkydoe
It's often also wise before you start to do a rational root test:

Let $f(x)=x^4-2x^3-2x^2+8x-8$

Suppose $f(x) =0$ has rational roots then it either has to be $x=\pm 1, \pm 2,\pm 4,\pm 8$.

I checked for you and notice that $f(2)=f(-2) = 0$ ! This means you can allready factor out $f(x)/(x-2)(x+2) = x^2-2x+2$.

For the other function $g$ we have $g(\pm 2)\neq 0$. This means that you only have to check whether the roots of $x^2-2x+2$ are roots of g(x) and you're done.

Edit: I can better put it like this. It now follows that gcd $(g(x),f(x)) =$gcd( $g(x), x^2-2x+2)$
• Jan 22nd 2010, 09:45 AM
qmech
Your first step was the first step in Euclidean factorization:

$

x^5 - 2x^4 - 3x^3 + 13x^2 -16x + 6 = x(x^4 - 2x^3 - 2x^2 + 8x - 8) + (-x^3 +5x^2-8x+6)
$

Now you have to do this again, but with the polynomials:
$

x^4 - 2x^3 - 2x^2 + 8x - 8 = (-x)(-x^3 +5x^2-8x+6) + remainder
$

Keep going until the remainder is 0.
• Jan 22nd 2010, 09:58 AM
Dinkydoe
Quote:

Your first step was the first step in Euclidean factorization:

http://www.mathhelpforum.com/math-he...3875a606-1.gif

Now you have to do this again, but with the polynomials:
http://www.mathhelpforum.com/math-he...c12a87dd-1.gif

Keep going until the remainder is 0.
That is clearly impossible: Only possible when $g(x) = f(x)\cdot p(x)$ For some linear factor $p(x)$. This is not the case here, there will allways be a remainder.