Let $a,b,n \in \mathbb{Z}$ with $n > 0$ and $a \equiv b \pmod n$. Show that $gcd(a, n) = gcd(b, n)$.

Given $a \equiv b \pmod n$,

$\mspace20pt$ $a - b = y \cdot n \mspace10pt$ for some $y \in \mathbb{Z}$

Observe $gcd(a, n)$ divides both the left hand side and right hand side. Therefore, $gcd(a, n)$ must divide both $b$ and $n$, which means

$\mspace20pt$ $gcd(a, n) \le gcd(b, n)$

Similar argument applies to $gcd(b,n)$ which divides both sides, and therefore,

$\mspace20pt$ $gcd(b, n) \le gcd(a, n)$

Thus, $gcd(a, n) = gcd(b, n)$

$\Box$

# posted by rot13(Unafba Pune) @ 10:57 PM