# Greatest common divisor of two numbers, $a$ and $b$

Suppose that $k,m,n \in \mathbb{N}$ s.t. gcd($m,n) = 1$. Also, let $a =$ gcd ($k,m)$ and $b =$ gcd ($k,n)$ and $k|mn$. We want to show that gcd($a,b) = 1$.

This question has multiple parts, but I am only asking to find the gcd($a,b) = 1$. What I know so far is that in order for the desired result to hold, $a$ and $b$ have to be relatively prime (otherwise, their greatest common divisor will not be $0$, but this isn't the case.) Thus, be Bezout's Lemma, $\exists x,y \in \mathbb{Z}$ s.t.

$$kx+my = a$$

and similarly, $\exists p,q \in \mathbb{Z}$ s.t. $$kp + nq = b$$

Perhaps I am making this more complicated than needed, but I don't see a clear path to achieve the desired result. How should one approach this? I know that that $m$ and $n$ are relatively prime, so this fact has to appear in the explanation somewhere.

• No need to invoke Bezout. If $p\,|\,\gcd(a,b)$ then $p\,|\,m$ and $p\,|\,n$. – lulu Mar 21 '18 at 22:41

By definition $a$ is a factor of $m$ and $b$ is a factor of $n$. Any common factor of $a$ and $b$ is therefore a common factor of $m$ and $n$. The only such (positive) common factor is $1$.
• I can see why $a$ is a factor of $m$, but why is $b$ a factor of $m$ as well, even though the gcd involves only $k$ and $n$? – John Smith Mar 21 '18 at 23:21