By definition $x=km+y$ for some $k \in \mathbb{Z}$. Let $d=gcd(x,m)$. By definition $d|x$ which implies that $d|km+y$. Since $d$ also devides $m$ we note that $d|y$. now suppose there is some larger $d'$ such that $d'|y$ and $d'|m.$ however since $y= x-km$ this would imply that $d'|x$ as well, contradicting the fact that d is the gcd of $x$ and $m.$ I was wondering if my proof is correct and also if the converse also true and if it is true, how could we prove it?
Asked
Active
Viewed 816 times
2
-
The converse is very false, so you should be able to find a counterexample. – Ben Millwood Mar 08 '14 at 20:26
2 Answers
2
Starting from what you had, let $x = km + y$. If $d|m$ also divides x, then $d|km+y$. Since it already divides km then it divides x if and only if it divides y. Now let d be GCD(y,m).
Flowers
- 775
- 4
- 13
0
Rerrange like this: $ $ if $\,d\mid m\,$ then $\, d\mid x\!\iff\! d\mid y,\,$ since $\,d\mid m\mid x\!-\!y.\,$ Hence $\,m,x\,$ and $\,m,y\,$ have the same set $\,S\,$ of common divisors $\,d,\,$ so the same greatest common divisor $(= {\rm max}\,S.)$
Bill Dubuque
- 272,048