# Prove $(b,m)=(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)$.

-
If an answer is good enough to accept, is it not also good enough to upvote? –  robjohn Sep 7 '12 at 19:27

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?

-

Hint $\$ If $\rm\,d\:|\:m\:$ then $\rm\:d\:|\:b\!\iff\! d\:|\:c,\:$ since $\rm\:d\:|\:m\:|\:b\!-\!c\:\Rightarrow\:b\equiv c\pmod d.$

Therefore $\rm\,m,b,\,$ and $\rm\,m,c\,$ have the same set S of common divisors $\rm\,d,\,$ so they necessarily have the same greatest common divisor, namely max S.

Remark $\$Alternatively, we may use the Bezout characterization of the gcd of $\rm\:m,b\:$ as the least positive integer in $\rm\: m\,\Bbb Z + b\,\Bbb Z. \:$ Thus $\rm\:(m,b) = (m,c)\:$ will follow from $\rm\: m\,\Bbb Z + b\,\Bbb Z\, =\, m\,\Bbb Z + c\,\Bbb Z.\:$
Proof: $\rm\ m\:j+ bk = m\:j + (b-c)k + ck = m\,(j+k(b\!-\!c)/m) + ck,\:$ so $\rm\:m\,\Bbb Z + b\,\Bbb Z \subset m\,\Bbb Z + c\,\Bbb Z.\:$ Finally, the reverse inclusion follows by $\rm\,b\leftrightarrow c\,$ symmetry.

-
@Serial Downvoter: if something is not clear please feel free to ask for elaboration. –  Bill Dubuque Sep 8 '12 at 0:59

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.

-

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

-