If $a \equiv b\pmod m$, then $\gcd(a, m) = \gcd(b, m)$ I was wondering if my proof makes any sense.
$a \equiv b \pmod m$
$ m \mid a -b$
$ ml = a - b$ for some integer $l$
let $d = \gcd(a, m)$
let $c = \gcd(b, m)$
$$\frac{a}{d} = \frac{m}{d}l - \frac{b}{d} \Rightarrow - \frac{a}{d} + \frac{ml}{d} = \frac{b}{d} \Rightarrow d \mid b \Rightarrow d  \leq c$$
Similarly, $c \mid a$, which means $c \leq d$
Thus, $c = d \Rightarrow \gcd(a, m) = \gcd(b, m)$.

Yes, that works. Quicker: if $\rm\: d\mid m\:$ then $\rm\:d\mid a\!\iff\! d\mid a+mk.\:$ So $\rm\ m,\,a\ $ and $\rm\ m,\,a\!+\!mk\ $ have the same set D of common divisors $\rm\,d,\,$ so they have the same greatest common divisor (= max D).
