Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
If an answer is good enough to accept, is it not also good enough to upvote? – robjohn Sep 7 '12 at 19:27
up vote 3 down vote accepted

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?

share|cite|improve this answer

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.

share|cite|improve this answer
@Serial Downvoter: if something is not clear please feel free to ask for elaboration. – Bill Dubuque Sep 8 '12 at 0:59

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.