# Thread: gcd / hcf of polynomial

1. ## gcd / hcf of polynomial

In lectures this week we were studying highest common factors (greatest common divisors) of polynomials. We went through all of the proofs, but we didn't actually do an example - and now that I've been set one, I'm a bit lost!

I found the Wikipedia page on calculating them, and there are two methods: factoring and the Euclidian algorithm. I don't think I'm supposed to use factoring - the questions set are of degree 4 / 5. So, that leaves me with the algorithm. Found here. However, I don't understand how the example they do in that table relates to the algorithm that is specified nearer the top of the article. Would someone be able to explain it step by step, or make up another example and go through it?

Thanks guys!

2. Originally Posted by storm123
In lectures this week we were studying highest common factors (greatest common divisors) of polynomials. We went through all of the proofs, but we didn't actually do an example - and now that I've been set one, I'm a bit lost!

I found the Wikipedia page on calculating them, and there are two methods: factoring and the Euclidian algorithm. I don't think I'm supposed to use factoring - the questions set are of degree 4 / 5. So, that leaves me with the algorithm. Found here. However, I don't understand how the example they do in that table relates to the algorithm that is specified nearer the top of the article. Would someone be able to explain it step by step, or make up another example and go through it?

Thanks guys!
Give an example from your homework. If you know Euclidean algorithm for integers this is exactly the same. You just keep on using the division algorithm. Here you will keep on doing polynomial division until you get a remainder of zero. It is exactly the same, just pretend those polynomials are numbers and see what happens.

3. Originally Posted by ThePerfectHacker
Give an example from your homework. If you know Euclidean algorithm for integers this is exactly the same. You just keep on using the division algorithm. Here you will keep on doing polynomial division until you get a remainder of zero. It is exactly the same, just pretend those polynomials are numbers and see what happens.

$\displaystyle \begin{array}{l} f\left( x \right) = {x^4} + {x^3} + 2{x^2} - 2x - 8 \\ g\left( x \right) = {x^4} - {x^3} + {x^2} + 2x - 6 \\ \end{array}$

4. Originally Posted by storm123

$\displaystyle \begin{array}{l} f\left( x \right) = {x^4} + {x^3} + 2{x^2} - 2x - 8 \\ g\left( x \right) = {x^4} - {x^3} + {x^2} + 2x - 6 \\ \end{array}$
I do one which is faster.

Let $\displaystyle f(x) = x^2 + 2x + 1$ and $\displaystyle g(x) = x^2 + 3x + 2$.

$\displaystyle x^2 + 3x + 2 = (1)(x^2+2x+1) + (x+1)$ ---> $\displaystyle \gcd(x^2+3x+2,x^2+2x+1) = \gcd(x^2+2x+1,x+1)$
$\displaystyle x^2 + 2x + 1 = (x+1)(x+1) + 0$ ---> $\displaystyle \gcd(x^2+2x+1,x+1) = x+1$

Therefore, the greatest common divisor is $\displaystyle x+1$.

Do you see how this is related to the standard Euclidean algorithm?