Let $n>0$ and $m>0$ be integers, and let $c = \gcd(n,m).$ Show that $\gcd\left(\frac{n}{c},\frac{m}{c}\right) = 1.$

Question

Let $n>0$ and $m>0$ be integers, and let $c = \gcd(n,m).$ Show that $$\gcd\left(\frac{n}{c},\frac{m}{c}\right) = 1.$$

I attempted using the idea that we know from definition of $gcd$ that we get

$n=ca$ and $m=cb$ for some unique values of $a,b \in \mathbb{Z}$.

And then I solved for $a,b$, giving $a=n/c,b=m/c$

I'm not really sure how to proceed without using a circular argument.

Answer 1

Hint: Assume that the gcd is not one, call it $l$. Then show that $cl$ also divides both $m$ and $n$ which leads to a contradiction.

Answer 2

We know that if $\gcd(m,n)=c$, then by Bezouts Identity there exist integers $a$ and $b$ with $$ am+bn=c. $$ Dividing through by $c$, we get $$ a\frac{m}{c}+b\frac{n}{c}=1. $$ This gives the desired result.

Answer 3

Other given answers are straightforward proofs, but this argument, although not as direct, might provide more insight in what is going on.

Assume $$x = p_1\cdots p_nq_1\cdots q_k$$ $$y = p_1\cdots p_nr_1\cdots r_l$$ where $p$'s, $q$'s and $r$'s are distinct primes. Obviously, $c = \gcd(x,y) = p_1\cdots p_n$ and $\frac xc, \frac yc$ share no common primes and thus are coprime.

Answer 4

Let $d=\gcd (a,b)$. Then $a=d a'$ and $b= d b'$ where $a',b'$ are integers. So $n=(c d)a'$ and $m=(c d)b'$ so $c d$ divides both $n$ and $m$ so, by definition of $c$, we have $1\leq c d\leq c$, so $d=1$.