prove if x ≡ y (mod m) then GCD(x, m) = GCD(y, m)

Question

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?

Answer 1

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).

Answer 2

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.)$