show that if a,b and c are integers with c>0 such that a is conguent to b (mod c), then (a,c)=(b,c)
$\displaystyle a \equiv b \pmod n $ $\displaystyle \Rightarrow $ $\displaystyle n | (a - b) $ $\displaystyle \Rightarrow $ $\displaystyle a = b + xn $ where $\displaystyle x \in \mathbb{Z} $
so $\displaystyle (a,n) = (b+xn,n) = (b,n) $
The justification for the last equality is left as an exercise (it's really easy)
Hope this helps,
pomp.