# Thread: Polynomial rings - GCD

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

2. ## Re: Polynomial rings - GCD

over what ring?

3. ## Re: Polynomial rings - GCD

My apologies!

The polynomials are over Q

Peter

4. ## 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

5. ## 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.

6. ## Re: Polynomial rings - GCD

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.

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