Results 1 to 7 of 7
Like Tree3Thanks
  • 1 Post By ibdutt
  • 1 Post By Deveno
  • 1 Post By Deveno

Math Help - Polynomial rings - GCD

  1. #1
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    558
    Thanks
    2

    Polynomial rings - GCD

    Let f(x) = 2x^3 + 2x^2 -x -1

    and let  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).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,275
    Thanks
    667

    Re: Polynomial rings - GCD

    over what ring?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    558
    Thanks
    2

    Re: Polynomial rings - GCD

    My apologies!

    The polynomials are over Q

    Peter
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jul 2012
    From
    INDIA
    Posts
    826
    Thanks
    209

    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
    Thanks from Bernhard
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,275
    Thanks
    667

    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.
    Thanks from Bernhard
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,275
    Thanks
    667

    Re: Polynomial rings - GCD

    Quote Originally Posted by ibdutt View Post
    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.
    Thanks from Bernhard
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    558
    Thanks
    2

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. polynomial rings
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: December 12th 2009, 02:35 PM
  2. Polynomial rings
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 29th 2009, 09:13 AM
  3. Polynomial Rings
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 10th 2009, 09:57 PM
  4. Polynomial Rings
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: May 8th 2009, 10:41 PM
  5. polynomial rings
    Posted in the Advanced Algebra Forum
    Replies: 9
    Last Post: February 28th 2009, 09:42 PM

Search Tags


/mathhelpforum @mathhelpforum