Let

and let

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).

Printable View

- December 25th 2012, 07:58 PMBernhardPolynomial rings - GCD
Let

and let

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). - December 25th 2012, 09:00 PMDevenoRe: Polynomial rings - GCD
over what ring?

- December 25th 2012, 10:08 PMBernhardRe: Polynomial rings - GCD
My apologies!

The polynomials are over Q

Peter - December 25th 2012, 10:27 PMibduttRe: 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 - December 25th 2012, 10:59 PMDevenoRe: 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)) = 2x^{4}- x^{2}- x(2x^{3}+ 2x^{2}- x - 1) = 2x^{4}- x^{2}- 2x^{4}- 2x^{3}+ x^{2}+ x

= -2x^{3}+ 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) = 2x^{4}- x^{2}- (x - 1)(2x^{3}+ 2x^{2}- x - 1) = 2x^{4}- x^{2}- 2x^{4}+ 3x^{2}- 1 = 2x^{2}- 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)) = 2x^{3}+ 2x^{2}- x - 1 - x(2x^{2}- 1) = 2x^{3}+2x^{2}- x - 1 - 2x^{3}+ x = 2x^{2}- 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) = 2x^{3}+2x^{2}- x - 1 - (x + 1)(2x^{2}- 1) = 2x^{3}+2x^{2}- x - 1 - 2x^{3}- 2x^{2}+ 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)) = 2x^{2}- 1. you may (if you wish) verify that 2x^{2}- 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) = 2x^{2}- 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. - December 25th 2012, 11:00 PMDevenoRe: Polynomial rings - GCD
- December 25th 2012, 11:07 PMBernhardRe: 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