Take the 2-minute tour ×
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.

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|improve this question
1  
If an answer is good enough to accept, is it not also good enough to upvote? –  robjohn Sep 7 '12 at 19:27
add comment

4 Answers 4

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|improve this answer
add comment

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.