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
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).
over what ring?
My apologies!
The polynomials are over Q
Peter
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
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.
-1/x is NOT a polynomial.Quote:
Originally Posted by ibdutt
Thanks.
Will now work through this post.
I was looking for a general approach and the theory behind it so thanks again!
Peter