1. ## GCDs of polynomials

Hi,
I'm to find the GCD of two polynomials, f(x) and g(x) in the field of integers mod 5, and then write it as a linear combination using the polynomials.
$\displaystyle f(x)=x^2 +2$ and $\displaystyle g(x)=x^3+4x^2+x+1$

I've found that the gcd $\displaystyle = 1 = (x^2 + 2) - [(-x +3)(-x+2)]$, but I'm having a lot of trouble turning that into the correct answer which is:
$\displaystyle (4x^2 + 3x + 4)(f(x) - (4x +2)g(x))$.

Did I make a mistake somewhere? Thanks for any help.

2. Originally Posted by kimberu
Hi,
I'm to find the GCD of two polynomials, f(x) and g(x) in the field of integers mod 5, and then write it as a linear combination using the polynomials.
$\displaystyle f(x)=x^2 +2$ and $\displaystyle g(x)=x^3+4x^2+x+1$

I've found that the gcd $\displaystyle = 1 = (x^2 + 2) - [(-x +3)(-x+2)]$

What does this mean?? Certainly the gcd is 1, but what is the right hand?

but I'm having a lot of trouble turning that into the correct answer which is:
$\displaystyle (4x^2 + 3x + 4)(f(x) - (4x +2)g(x))$.

Did I make a mistake somewhere? Thanks for any help.

You must do exactly the same as with integers when applying Euclides' Algorithm: divide and divide until you get the gcd, and then go backwards and write each remainder as a linear combination of the other stuff...

$\displaystyle x^3+4x^2+x+1=(x+4)(x^2+2)+(4x+3)$

$\displaystyle x^2+2=(4x+2)(4x+3)+1$

And we're done since the remainder now is a unit (i.e., the reaminder is 1), so now go backwards (some parentheses are for clearity's sake):

$\displaystyle 1=(x^2+2)-(4x+2)(4x+3)=(x^2+2)-(4x+2)\left[(x^3+4x^2+x+1)-(x+4)(x^2+4)\right]$ $\displaystyle =(x^2+2)-(4x+2)(x^3+4x+x+1)+(4x^2+3x+3)(x^2+2)=$ $\displaystyle (4x^2+3x+4)(x^2+2)-(4x+2)(x^3+4x^2+x+1)$

Of course, instead $\displaystyle -(4x+2)(...)$ you can write $\displaystyle +(x+3)(...)$

Tonio

3. Thank you so much! what I had with $\displaystyle 1 = (x^2 + 2) - [(-x +3)(-x+2)]$
corresponds with your first line going backwards: $\displaystyle 1=(x^2+2)-(4x+2)(4x+3)$. I didn't realise I should use 4x instead of -x, but that certainly helped with my multiplication troubles! Thanks!!