# GCD of the already GCD

Say $a$ and $b$ are integers. $\gcd(a,b)$ is then $d$. Now if $a$ equals $dm$ for some integer $m$ and b equals $dn$ for some integer n, how come the gcd of this m and n is always 1?

Suppose that $\ell$ divides both $m$ and $n$. Then we can write $m=\ell\cdot\tilde{m}$ and $n=\ell\cdot\tilde{n}$, and therefore $a=d\ell\tilde{m}$ and $b=d\ell\tilde{n}$. But then $d\ell$ divides both $a$ and $b$; but if $\ell>1$, then $d\ell>d$, contradicting the assumption that $d$ was the greatest common divisor. So, it must be the case that $\ell=1$.

• Looking at this, but does the m and n with the squiggly line on top mean 'factor of m' and 'factor of n'?
– Paze
Jan 20, 2014 at 19:22
• It's just another symbol. We could also use $h$ and $k$. I just used those so that it was clear with which variable each was associated. Jan 20, 2014 at 19:24
• @Paze : They are simply the division of $m$ with $\el$ and $n$ with $\el$. He could have written $m'$ or anything. Jan 20, 2014 at 19:25
• Thank you. This seems clear. But don't you mean b=dln?
– Paze
Jan 20, 2014 at 19:25
• @Paze Good spot. Fixed. Jan 20, 2014 at 19:26

$d\mid a,b,\,\ c\mid \overbrace{a/d}^{\large m},\,\overbrace{b/d}^{\large n} \ \overset{\large \times\,d}\Rightarrow\, cd\mid a,b\,\Rightarrow\!\!\!\!\!\!\!\!\!\overbrace{cd\,\le\, \gcd(a,b),}^{\large \rm gcd\ =\ {\bf max}\ common\ divisor}\!\!\!\!\!\!\!\!\!$ so $\,d=\gcd(a,b)\, \Rightarrow\, c = 1.\ \$ QED

Remark  This is a special case of the GCD Distributive Law $\ (ac,bc) = (a,b)c.\,$ Applied here we deduce $\ d = (md,nd) = (m,n)d\iff (m,n) = 1.$