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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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$.
answered Jan 20, 2014 at 19:20
-
$\begingroup$ Looking at this, but does the m and n with the squiggly line on top mean 'factor of m' and 'factor of n'? $\endgroup$– PazeJan 20, 2014 at 19:22
-
$\begingroup$ 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. $\endgroup$ Jan 20, 2014 at 19:24
-
$\begingroup$ @Paze : They are simply the division of $m$ with $\el$ and $n$ with $\el$. He could have written $m'$ or anything. $\endgroup$ Jan 20, 2014 at 19:25
-
$\begingroup$ Thank you. This seems clear. But don't you mean b=dln? $\endgroup$– PazeJan 20, 2014 at 19:25
-
$\begingroup$
$\endgroup$
$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.$
answered Jan 20, 2014 at 20:48