Prove: If x≡y (mod m), then (m,x) = (m,y) The question is to prove if x≡y (mod m), then (m,x) = (m,y). I think that I should start by showing that m|x-y and by the definition of division x-y=mq for some integer q. If I let d=(m,x) then I know that d is a linear combination of m and x such that d=mr+xs for some integers r,s. I can substitute to get d=mr+(mq+y)s=mr+mqs+ys. So now I have d=m(r+qs)+ys. Does that show, by BeZout's identity that d=(m,y)? Or am I wrong?
Hint $\ $ If $\ d\mid m\ $ and $\ x-y = km\ $ then $\ d\mid x\iff d\mid y.\,$ Therefore $\,m,x\,$ and $\,m,y\,$ have the same set $\,S\,$ of common divisors $\,d,\,$ hence the same greatest common divisor (= max $S).$
We know m|x-y => mk=x-y. Also
(m,x)=d => m=dk1, x=dk2. If we put these in the first equation (mk=x-y) we have: dk1k=dk2-y => y=d(k2-k1k) => d|y. So d divides y. Therefore, d|(y,m) => (x,m)|(y,m). (1)

In the same way we can show that (y,m)|(x,m). (2)

Considering (1) and (2) we can say (x,m)=(y,m).