# Math Help - congruence problem

1. ## congruence problem

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)

2. $a \equiv b \pmod n$ $\Rightarrow$ $n | (a - b)$ $\Rightarrow$ $a = b + xn$ where $x \in \mathbb{Z}$

so $(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.