Results 1 to 7 of 7

Math Help - GCD question

  1. #1
    Junior Member
    Joined
    Nov 2010
    Posts
    40

    GCD question

    if m>0

    show that

    m(a,b)=(ma,mb)

    I'm told that (ma,mb) = max + mby = m(ax + by) = m(a,b)
    isn't sufficient... why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by gutnedawg View Post
    if m>0

    show that

    m(a,b)=(ma,mb)

    I'm told that (ma,mb) = max + mby = m(ax + by) = m(a,b)
    isn't sufficient... why?
    \text{let} \ d=\text{gcd}(ma,mb) \ \ \text{and} \ \ c=\text{gcd}(a,b)

    d=max+mby \ \ x,y\in\mathbb{Z} \ \ \ mc=maz+mbt \ \ z,t\in\mathbb{Z}

    d|ma \ \ \text{and} \ \ mc|ma\Rightarrow mc|d

    Now, all you have to do is show d|mc and you can then say d=mc and you are done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    how do I show d|mc?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by gutnedawg View Post
    how do I show d|mc?
    d divides the LHS of mc=maz+mbt; therefore, d|RHS
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2010
    Posts
    40
    but we have shown that mc|d not d|mc so I'm not sure how you come to this conclusion

    never mind: since d=(ma,mb) thus d|max+mby for any x,y in Z correct?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Quote Originally Posted by gutnedawg View Post
    if m>0

    show that

    m(a,b)=(ma,mb)

    I'm told that (ma,mb) = max + mby = m(ax + by) = m(a,b)
    isn't sufficient... why?
    Maybe to answer your original question, the bad part of your proof is here: m(ax+by)=m(a,b). The only thing that you can conclude about the number ax+by is that it is a multiple of (a,b), which is a little bit too weak to prove what you want.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by gutnedawg View Post
    if m>0

    show that

    m(a,b)=(ma,mb)

    I'm told that (ma,mb) = max + mby = m(ax + by) = m(a,b)
    isn't sufficient... why?

    Let d=(a,b) be the greatest common divisor of a and b . So, d is the smallest positive integer that can be expressed a linear combination of a and b .(Theorem.)

    Consider the following linear combinations : (ma)x+(mb)y=m(ax+by), where x,y are integers.

    From the equation we can see that (ma)x+(mb)y is the smallest positive linear combination of ma and mb precisely when ax+by is the smallest positive linear combination of a and b . Applying the theorem we have (ma,mb)=m(a,b).
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum