1. ## 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.

2. Originally Posted by jimmyjimmyjimmy
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.