# Thread: Highest common factor, Polynomial division

1. ## Highest common factor, Polynomial division

Hi, think this is the correct forum, apologies if not.

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

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

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

$\displaystyle 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?

2. Edit just seen that I've not fully completed the algorithm yet! Think I can manage this..

3. I wondered about that- because what you wrote involved neither factoring nor long division!

4. Yeh sorry about that. Posted the question and then realised that I'd only done the first bit... oops.

5. It's often also wise before you start to do a rational root test:

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

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

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

For the other function $\displaystyle g$ we have $\displaystyle g(\pm 2)\neq 0$. This means that you only have to check whether the roots of $\displaystyle 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$\displaystyle (g(x),f(x)) =$gcd($\displaystyle g(x), x^2-2x+2)$

6. Your first step was the first step in Euclidean factorization:

$\displaystyle 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:
$\displaystyle x^4 - 2x^3 - 2x^2 + 8x - 8 = (-x)(-x^3 +5x^2-8x+6) + remainder$

Keep going until the remainder is 0.

7. Your first step was the first step in Euclidean factorization:

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

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