Results 1 to 2 of 2

Thread: 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 $\displaystyle gcd(a,b) = d$, then there exist integers $\displaystyle x$ and $\displaystyle y$ such that $\displaystyle ax + by = d$.

    We can use Bezout's identity here and the proof will be very simple.
    Let $\displaystyle gcd(k,n) = d_1$ and $\displaystyle gcd(k, m) = d_2$, then there exists integers $\displaystyle x_1, y_1$ and $\displaystyle x_2$, $\displaystyle y_2$ such that $\displaystyle x_1k + y_1n = d_1$ and $\displaystyle x_2k + y_2m = d_2$.
    Then we multiply $\displaystyle 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 $\displaystyle k$ divides each term in this equation hence $\displaystyle k|gcd(k,n)*gcd(k,m)$, as required.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum