# How do I show that if two gcds are the same, then their values are the same?

I want to show that for $\gcd(m,n) = \gcd(p,q) = 1$, if $qm = pn$ then $m=p$ and $n=q$.

Here is what I am working through:

1. If both the gcds are equal to 1, then I can express $\gcd(m,n)$ as a linear combination of m and n, and likewise for $\gcd(p,q)$.
2. If I multiply these two linear combinations, I can still get a value of 1 but it will result in complicated algebra.

However, if I try this method:

1. I let $qm - pn = 0$. Since the two gcds can divide 0, then naturally they have the same value. I know that this is a linear combination of both q and p, and m and n.

But it seems that this approach also means any gcd can divide qm-pn. So I'm unable to proceed further to show that $m=p$ and $n=q$.

• – Barry Cipra Jan 8 '18 at 13:26

We know $am+bn=1$ for some $a,b$, so $pam+pbn=p$.
But $pbn=bqm$, so $(pa+bq)m=p$, giving $m\mid p$.
Similarly you can show the reverse, and for $q,n$.
• Thanks for the hint. But doesn't this only show that $m | p$ and not $m = p$? – oldselflearner1959 Jan 8 '18 at 13:27
• @oldselflearner1959 You have to show four divisibilities : $m|p$ , $p|m$ , $n|q$ , $q|n$. You just have to use $$\gcd(a,b)=1\ and\ a|bc\implies a|c$$ – Peter Jan 8 '18 at 13:32
• Note that for positive integers $a,b$ , $a|b$ AND $b|a$ implies $a=b$. – Peter Jan 8 '18 at 13:34