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

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.
