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.

  • 1
    $\begingroup$ No need to invoke Bezout. If $p\,|\,\gcd(a,b)$ then $p\,|\,m$ and $p\,|\,n$. $\endgroup$ – 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$.

  • $\begingroup$ 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$? $\endgroup$ – John Smith Mar 21 '18 at 23:21
  • 1
    $\begingroup$ Typo, fixed now. Thanks for pointing it out. $\endgroup$ – David Mar 22 '18 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.