Results 1 to 2 of 2

Math Help - gcd

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    gcd

    Hi,

    Let k>1.
    Show that if k divides nm, then k divides gcd(k,n)*gcd(k,m)

    This result is easy to think about, but I'm having a hard time making it formal. I'm pretty sure the best way is to look at the prime factorizations of k, n, and m. Each prime which divides k must also divide either n or m. So the product gcd(k,n)*gcd(k,m) will contain all prime factors of k. That seems like hand waving though, I don't know exactly how to make it a solid argument. Any hints would be appreciated. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member utopiaNow's Avatar
    Joined
    Mar 2009
    Posts
    72
    Thanks
    1
    Quote Originally Posted by jimmyjimmyjimmy View Post
    Hi,

    Let k>1.
    Show that if k divides nm, then k divides gcd(k,n)*gcd(k,m)

    This result is easy to think about, but I'm having a hard time making it formal. I'm pretty sure the best way is to look at the prime factorizations of k, n, and m. Each prime which divides k must also divide either n or m. So the product gcd(k,n)*gcd(k,m) will contain all prime factors of k. That seems like hand waving though, I don't know exactly how to make it a solid argument. Any hints would be appreciated. Thanks.
    Are you aware of Bezout's identity? It states that if gcd(a,b) = d, then there exist integers x and y such that ax + by = d.

    We can use Bezout's identity here and the proof will be very simple.
    Let gcd(k,n) = d_1 and gcd(k, m) = d_2, then there exists integers x_1, y_1 and x_2, y_2 such that  x_1k + y_1n = d_1 and x_2k + y_2m = d_2.
    Then we multiply d_1*d_2 = (x_1k + y_1n )(x_2k + y_2m) = k^2x_1x_2 + x_1y_2km + y_1x_2kn + y_1y_2mn. Now you see that k divides each term in this equation hence k|gcd(k,n)*gcd(k,m), as required.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum