# Thread: Congruence & Modulo Proof

1. ## Congruence & Modulo Proof

Show that if a, b, and m are integers such that m >= 2 and a is congruent to b mod m then GCD(a, m) = GCD(b, m)

2. Recall the definition of GCD: $d=\gcd(r,s)$ iff (i) $d\mid r$ and $d\mid s$ and (ii) $\forall\,c\in\mathbb Z,$ $c\mid r$ and $c\mid s$ $\Rightarrow$ $c\mid d.$

Now, $a\equiv b\pmod m$ $\Rightarrow$ $a=b+km$ for some $k.$

Let $d=\gcd(a,m).$

(i) $d\mid a$ and $d\mid m$ $\Rightarrow$ $d\mid a-km=b$

$\therefore\ d\mid b$ and $d\mid m$

(ii) Suppose $c\mid b$ and $c\mid m.$ Then $c\mid b+km=a.$ So $c\mid a$ and $c\mid m;$ $\therefore\ c\mid\gcd(a,m)=d.$

(i) and (ii) $\Rightarrow$ $d=\gcd(b,m)$