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)$.
 A: If $d$ is a common divisor of $b$ and $m$, and $a = b + m l$, then $d$ also divides $a$, and thus divides $a$ and $m$. 
By symmetry, the converse also holds, so the set of common divisors of $a, m$, and that of $b, m$ is the same, hence the two $\gcd$ are also the same.
This is basically your proof, without resorting to fractions, and without the need to go through inequalities, it's just a matter of divisibility.
A: 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).
A: If $a\equiv b \pmod m$ (so that $a-b=km$ for some $k\in \mathbb{Z}$) then $$ a\mathbb{Z}+m\mathbb{Z}=b\mathbb{Z}+m\mathbb{Z}$$ because $$a\mathbb{Z}+m\mathbb{Z} \ni ap+mq = bp +mq +(a-b)p= bp+ m(q+kp)\in b\mathbb{Z}+m\mathbb{Z}$$ and the other inclusion is similar. The result then follows since $\gcd(r,s)$ is the least positive element of $r\mathbb{Z}+s\mathbb{Z}.$
