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.


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

  • 1
    $\begingroup$ 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. $\endgroup$ Mar 5 '13 at 19:34
  • $\begingroup$ @Andreas Indeed, I often promote the universal definitions of gcd, lcm here, e.g. a recent example. The above proof works either way, whether one reads it as max absolute value, or maximal wrt to divisibility. $\endgroup$
    – Math Gems
    Mar 5 '13 at 19:43

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.