Prove $\,b\equiv c\pmod{\!m}\Rightarrow \gcd(b,m)=\gcd(c,m)$ i.e. $\gcd(c+km,m) = \gcd(c,m)$

Solution 1:

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.

Solution 2:

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