# 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.
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).
• In view of generalizations (and also, but less importantly, to allow $\gcd(0,0)$), I believe to be preferable to define a gdc not as the largest common divisor, but as a common divisor that is divisible by all common divisors. Mar 5 '13 at 19:34
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}.$