# Polynomial rings - GCD

• Dec 25th 2012, 06:58 PM
Bernhard
Polynomial rings - GCD
Let \$\displaystyle f(x) = 2x^3 + 2x^2 -x -1\$

and let \$\displaystyle g(x) = 2x^4 - x^2\$

Find a(x) and b(x) such that

d(x) = a(x)f(x) + b(x)g(x)

where d(x) is the greatest common divisor of f(x) and g(x).
• Dec 25th 2012, 08:00 PM
Deveno
Re: Polynomial rings - GCD
over what ring?
• Dec 25th 2012, 09:08 PM
Bernhard
Re: Polynomial rings - GCD
My apologies!

The polynomials are over Q

Peter
• Dec 25th 2012, 09:27 PM
ibdutt
Re: Polynomial rings - GCD
f(x) = (2x^2 – 1 )(x+1)
g(x) = x^2(2x^2 – 1 )
GCD of f(x) and g(x) is ( 2x^2 – 1 ) so d(x) = ( 2x^2 – 1 )
Now it is given that d(x) = a(x) f(x) + b(x) g(x)
So we get: ( 2x^2 – 1 ) = (2x^2 – 1 )(x+1) a(x) + b(x) x^2(2x^2 – 1 )
Dividing throughout by (2x^2 – 1 ) we get
1 = (x+1) a(x) + b(x) x^2 OR (x+1) a(x) + b(x) x^2 = 1
By observation we can see that equation will be true only if a(x) = 1 and b(x) = -1/x
Verification: LHS = (x+1) a(x) + b(x) x^2 = (x+1) ( 1 ) + (- 1/x ) x^2 = x + 1 – x = 1 = RHS
• Dec 25th 2012, 09:59 PM
Deveno
Re: Polynomial rings - GCD
well Q[x] is euclidean. that's the key.

since g(x) has greater degree, we will divide g(x) by f(x), and keep track of our remainders.

so our first step is:

g(x) = q(x)(f(x)) + r(x) ,where deg(r) < deg(f) or r = 0. our first guess will be q(x) = x.

to find r(x) we simply subtract g(x) - x(f(x)) = 2x4 - x2 - x(2x3 + 2x2 - x - 1) = 2x4 - x2 - 2x4 - 2x3 + x2 + x

= -2x3 + x. this has the same degree as f, so our next step is guess q(x) = x - 1 (using a bigger coefficient of x won't help, so we go "the next power down").

r(x) = g(x) - q(x)f(x) = 2x4 - x2 - (x - 1)(2x3 + 2x2 - x - 1) = 2x4 - x2 - 2x4 + 3x2 - 1 = 2x2 - 1

now we have a proper remainder r(x).

to continue, we do the same process with f(x) and r(x). again, we'll try q'(x) = x as our first guess.

r'(x) = f(x) - x(r(x)) = 2x3 + 2x2 - x - 1 - x(2x2 - 1) = 2x3 +2x2 - x - 1 - 2x3 + x = 2x2 - 1.

obviously, this won't do, since deg(r') = deg(r), so we try q'(x) = x + 1.

then r'(x) = f(x) - q'(x)r(x) = 2x3 +2x2 - x - 1 - (x + 1)(2x2 - 1) = 2x3 +2x2 - x - 1 - 2x3 - 2x2 + x + 1 = 0

"back up one step", we find that gcd(g(x),f(x)) = gcd(f(x),r(x)) = r(x) (since r(x)|f(x)).

hence gcd(g(x),f(x)) = 2x2 - 1. you may (if you wish) verify that 2x2 - 1 does indeed divide both f(x) and g(x).

now we already have the means to find a(x) and b(x).

note that r(x) = 2x2 - 1 = g(x) - (x - 1)f(x), so a(x) = -x + 1, and b(x) = 1.

in other words, to find the gcd of two polynomials over a field, we proceed exactly like we find the gcd of two integers, "by long division".

reversing the division process lets us express every remainder in terms of previous remainders, and thus ultimately in terms of f and g.
• Dec 25th 2012, 10:00 PM
Deveno
Re: Polynomial rings - GCD
Quote:

Originally Posted by ibdutt
f(x) = (2x^2 – 1 )(x+1)
g(x) = x^2(2x^2 – 1 )
GCD of f(x) and g(x) is ( 2x^2 – 1 ) so d(x) = ( 2x^2 – 1 )
Now it is given that d(x) = a(x) f(x) + b(x) g(x)
So we get: ( 2x^2 – 1 ) = (2x^2 – 1 )(x+1) a(x) + b(x) x^2(2x^2 – 1 )
Dividing throughout by (2x^2 – 1 ) we get
1 = (x+1) a(x) + b(x) x^2 OR (x+1) a(x) + b(x) x^2 = 1
By observation we can see that equation will be true only if a(x) = 1 and b(x) = -1/x
Verification: LHS = (x+1) a(x) + b(x) x^2 = (x+1) ( 1 ) + (- 1/x ) x^2 = x + 1 – x = 1 = RHS

-1/x is NOT a polynomial.
• Dec 25th 2012, 10:07 PM
Bernhard
Re: Polynomial rings - GCD
Thanks.

Will now work through this post.

I was looking for a general approach and the theory behind it so thanks again!

Peter