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