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 $\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.