# 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: $\displaystyle d=\gcd(r,s)$ iff (i) $\displaystyle d\mid r$ and $\displaystyle d\mid s$ and (ii) $\displaystyle \forall\,c\in\mathbb Z,$ $\displaystyle c\mid r$ and $\displaystyle c\mid s$ $\displaystyle \Rightarrow$ $\displaystyle c\mid d.$

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

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

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

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

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

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