Results 1 to 5 of 5

Math Help - Coprime polynomials

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    50

    Coprime polynomials

    Can you help me with this problem:

    I have to prove that if gcd(f(x),g(x))=1 then there exist unique u(x) and v(x) such that u(x)f(x)+v(x)g(x)=1 and deg u(x)< deg g(x) , deg v(x)< deg f(x).

    This problem seems so strange. How to prove this?
    Last edited by andreas; November 23rd 2008 at 12:44 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2008
    Posts
    18
    this is just gcd of two polynomials. to prove unique suppose not then arrive at a contradiction. this is only an existence and uniqueness proof
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    50
    Quote Originally Posted by xianghu21 View Post
    this is just gcd of two polynomials. to prove unique suppose not then arrive at a contradiction. this is only an existence and uniqueness proof

    To be honest I thought the same.Indeed, this problem seems trivial. So I should take u(x)f(x)+v(x)g(x)=1 as grated without proof?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2008
    Posts
    25
    Existence is given by euclidean algorithm: Here it is: An important consequence of the Euclidean algorithm is finding integers and such that


    This can be done by starting with the equation for , substituting for from the previous equation, and working upward through the equations. Now just prove uniqueness. Then you are done. i.e. euclidean algorithm is valid for any ring of polynomials.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by andreas View Post
    Can you help me with this problem:

    I have to prove that if gcd(f(x),g(x))=1 then there exist unique u(x) and v(x) such that u(x)f(x)+v(x)g(x)=1 and deg u(x)< deg g(x) , deg v(x)< deg f(x).

    This problem seems so strange. How to prove this?
    those who replied to your question forgot that we also need to have \deg u(x) < \deg g(x) and \deg v(x) < \deg f(x). the problem is not trivial! anyway, i'll assume that the polynomials are over

    a field. we know that there exist polynomials u_1(x) and v_1(x) such that u_1(x)f(x) + v_1(x)g(x) = 1. now there exist polynomials u(x) and r(x) such that u_1(x)=r(x)g(x) + u(x), where either

    u(x)=0, or \deg u(x) < \deg g(x). also there exist polynomials v(x) and s(x) such that v_1(x)=s(x)f(x)+v(x), where either v(x)=0, or \deg v(x) < \deg f(x).

    so: (r(x) + s(x))f(x)g(x) + u(x)f(x) + v(x)g(x)=1, which is possible only if r(x) + s(x)=0. why? therefore: u(x)f(x) + v(x)g(x)=1, and the existence part is done. for the uniqueness

    suppose we have u(x)f(x) + v(x)g(x)=u'(x)f(x)+v'(x)g(x)=1, with \deg u(x) < \deg g(x), \ \deg v(x) < \deg f(x), and \deg u'(x) < \deg g(x), \ \deg v'(x) < \deg f(x). then we will have:

    (u(x)-u'(x))f(x)=(v'(x)-v(x))g(x). thus, since \gcd(f(x),g(x))=1, we must have f(x) \mid v'(x)-v(x), which is possible only if v(x)-v'(x)=0, because \deg(v(x)-v'(x)) < \deg f(x).

    hence v(x)=v'(x), and therefore: (u(x)-u'(x))f(x)=0, which gives us: u(x)=u'(x). \ \ \Box
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Coprime Polynomials
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 2nd 2011, 03:39 PM
  2. comaximal(coprime)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 15th 2010, 11:45 PM
  3. coprime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 13th 2009, 05:45 AM
  4. Coprime
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 11:32 AM
  5. More on coprime integers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2009, 06:30 PM

Search Tags


/mathhelpforum @mathhelpforum