Results 1 to 5 of 5

Math Help - gcd(ma,mb) = m gcd(a,b)

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

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

    Theorem:
    For any natural number m, gcd(ma,mb) = m gcd(a,b)

    Proof:
    Let N={natural numbers}
    By another theorem, we know that
    gcd(ma,mb)=min({m(ax)+m(by): x,y E Z} ∩ N)
    =m * min({ax+by: x,y E Z} ∩ N)
    =m * gcd(a,b)
    ===========================

    I don't understand the step
    min({m(ax)+m(by): x,y E Z} ∩ N) = m * min({ax+by: x,y E Z} ∩ N).
    Why is this true? Can someone please explain this?

    Thanks for any help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Theorem:
    For any natural number m, gcd(ma,mb) = m gcd(a,b)

    Proof:
    Let N={natural numbers}
    By another theorem, we know that
    gcd(ma,mb)=min({m(ax)+m(by): x,y E Z} ∩ N)
    =m * min({ax+by: x,y E Z} ∩ N)
    =m * gcd(a,b)
    ===========================

    I don't understand the step
    min({m(ax)+m(by): x,y E Z} ∩ N) = m * min({ax+by: x,y E Z} ∩ N).
    Why is this true? Can someone please explain this?

    Thanks for any help!
    Suppose that \tau=\min\left\{max+mby:x,y\in\mathbb{Z}\right\}\c  ap \mathbb{N}, then \tau=ma\tilde{x}+mb\tilde{y} for some \tilde{x},\tilde{y}\in\mathbb{Z}. I claim that a\tilde{x}+a\tilde{y}=\min\left\{ax+by:x,y\in\math  bb{Z}\right\}\cap\mathbb{N}. To see this assume it was false. Then there exists some ax'+by'\in\left\{ax+by:x,y\in\mathbb{Z}\right\}\ca  p\mathbb{N} such that ax'+by'\leqslant a\tilde{x}+b\tilde{y} but since m\in\mathbb{N} we see that this implies max'+mby'\leqslant ma\tilde{x}+mb\tilde{y} which contradicts the minimality of ma\tilde{x}+mb\tilde{y}. Thus, we have that \min\left\{max+mby:x,y\in\mathbb{Z}\right\}\cap\ma  thbb{N}=ma\tilde{x}+mb\tilde{y}=m\cdot\min\left\{a  x+by:x,y\in\mathbb{Z}\right\}\cap\mathbb{N}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Definition of gcd by linear combination:
    let a and b are two integers, then gcd(a,b) is the smallest positive integer which can be written as a linear combination of a and b over Z, that is, there exist integers x and y such that gcd(a,b)=ax+by.
    This is why the equality gcd(a,b)=min\{\{ax+by:x,y\in Z\}\cap N\} holds.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Drexel28 View Post
    Suppose that \tau=\min\left\{max+mby:x,y\in\mathbb{Z}\right\}\c  ap \mathbb{N}, then \tau=ma\tilde{x}+mb\tilde{y} for some \tilde{x},\tilde{y}\in\mathbb{Z}. I claim that a\tilde{x}+a\tilde{y}=\min\left\{ax+by:x,y\in\math  bb{Z}\right\}\cap\mathbb{N}. To see this assume it was false. Then there exists some ax'+by'\in\left\{ax+by:x,y\in\mathbb{Z}\right\}\ca  p\mathbb{N} such that ax'+by'\leqslant a\tilde{x}+b\tilde{y} but since m\in\mathbb{N} we see that this implies max'+mby'\leqslant ma\tilde{x}+mb\tilde{y} which contradicts the minimality of ma\tilde{x}+mb\tilde{y}. Thus, we have that \min\left\{max+mby:x,y\in\mathbb{Z}\right\}\cap\ma  thbb{N}=ma\tilde{x}+mb\tilde{y}=m\cdot\min\left\{a  x+by:x,y\in\mathbb{Z}\right\}\cap\mathbb{N}
    Thanks, that makes sense.

    But is there any "intuitive" way to understand the reason why we can factor the "m" out of the min?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Thanks, that makes sense.

    But is there any "intuitive" way to understand the reason why we can factor the "m" out of the min?
    What I said is very intuitive. It is just shrouded in formal language. Basically, the reason why we can factor the m out is that it doesn't contribute to the minimum. So, multiplying by a constant will not change the minimum of a set...except for multiplying it by the constant.

    Think about it like this. (this is really informal, and kind of incorrect)

    We can think about the one set as

    ax_1+by_1<ax_2+by_2<\cdots. Now, if I multiply by m I get amx_1+bmy_1<amx_2+bmy_2<\cdots so that the minimum of the second set is clearly going to just be m times the mimum of the first set.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum