Proof dealing with greatest common divisors

Question

I'm working on a proof which concludes that if $a\equiv b (mod\ m)$

then $gcd(a,m) = gcd(b,m)$

I know that we can rewrite the congruence as $km = a-b$ for some $k \in \mathbb{Z}$

I rearranged the equation to : $a = b + km$

So I have that:
$$gcd(b,m)|(b+km)$$ and
$$gcd(b,m)|a$$

I'm not sure where I'm supposed to go from here. I've been told that I can say that $$gcd(b,m) \leq gcd(a,m)$$ but I'm not sure how to draw that conclusion. Could someone explain that part?

Thanks!

Answer 1

Hint. Frequently, a good way to show that two positive integers are equal is to show that each is less than or equal to the other. Here is a sketch, see if you can supply the reasons and then complete the proof.

1. Let $g=\gcd(a,m)$. By definition, $g\mid a$ and $g\mid m$.
2. Then $g\mid b$, because...
3. So $g\le\gcd(b,m)$ because...
4. And can you now see what you still need to do?

Answer 2

Hint $\ $ If $\,d\mid m\,$ then $\,d\mid b\!+\!km\iff d\mid b.\,$ This implies that $\,m,\, b\!+\!km\,$ and $\,m,b\,$ have the same set $\,D\,$ of common divisors $\,d,\,$ thus they have the same greatest common divisor $(= \max D)$