Prove $\,b\equiv c\pmod{\!m}\Rightarrow \gcd(b,m)=\gcd(c,m)$ i.e. $\gcd(c+km,m) = \gcd(c,m)$ If $ b\equiv c \pmod m $ then prove that $(b,m)=(c,m)$.
My solution so far:   
If $b \equiv c \pmod m$ then $c = b - sm$ for some $s$. Now if $d = (b, m)$
then $ d |  (b + s m)$.
 A: Hint $\ $ If $\rm\,d\:|\:m\:$  then $\rm\:d\:|\:b\!\iff\! d\:|\:c,\:$ by $\rm\:b\equiv c\pmod{\! d},\,$ by $\rm\,d\:|\:m\:|\:b\!-\!c$
Therefore $\rm\,m,b,\,$ and $\rm\,m,c\,$ have the same set $\,\rm S\,$ of common divisors $\rm\,d,\,$ so they necessarily  have the same greatest common divisor $\rm (= \max\:\! S)$
Remark $\ $Alternatively, we may use the Bezout characterization of the gcd $\rm\,(m,b)\,$ as the least positive integer in $\rm\: m\,\Bbb Z + b\,\Bbb Z. \,$ Thus $\rm\:(m,b) = (m,c)\:$ follows from $\rm\: m\,\Bbb Z + b\,\Bbb Z\, =\, m\,\Bbb Z + c\,\Bbb Z,\,$
true by $\rm\  m\:j+ \color{#c00}bk = m\:j + (\color{#c00}{b\!-\!c})k + \color{#c00}ck = m\,(j+k(b\!-\!c)/m) + ck = m j' + ck,\:$ so $\rm\:m\,\Bbb Z + b\,\Bbb Z \,\subseteq\, m\,\Bbb Z + c\,\Bbb Z,\:$ and the reverse inclusion follows by $\rm\,b\leftrightarrow c\,$ symmetry.
In terms of ideal theory this may be viewed simply as a standard "change of basis", cf. Remark here.
A: Suppose that $b\equiv c\pmod{m}$. 
Suppose that  $x$ divides both $b$ and $m$. Since $c=b+km$ for some $k$, it follows that $x$ divides $c$. 
Similarly, if $x$ divides both $c$ and $m$, then $x$ divides $b$.
Thus every common divisor of $b$ and $m$ is a common divisor of $c$ and $m$, and vice-versa.
It follows that the greatest common divisor of $b$ and $m$ is the same as the greatest common divisor of $c$ and $m$.
A: You pointed out that $b=c+sm$ for some $s$.
Let $d=bx+my$ for some $x,y\in \mathbb{Z},\;\;d\in \mathbb{N}$. Then $d=cx'+my'$ for $x'=x,\;\;y'=y+sx$. Similarly  if $d=cx+my$ for some $x,y\in \mathbb{Z},\;\;d\in \mathbb{N}$ then $d=bx'+my'$ for $x'=x,\;\;y'=y-sx$.
Bearing in mind that $(b,m)=\min\{bx+my:x,y\in \mathbb{Z},bx+my>0\}$ the result follows.
A: Let $(b,m) = d$ and $(c,m) = d'$. If $b \equiv c \pmod m$ then $b = c + \lambda m$ for some $\lambda \in \mathbb{Z}$. We know that $d|b$ and $d|m$, so $d|(b-\lambda m)$ and so $d|c$ and hence $d|d'$.
Can you see where to take it from here?
