I need ideas on how to prove that if $a\equiv b\mod c$, then $(a,c)=(b,c)$, where $a$, $b$ and $c\in\mathbb{Z}$, $c0$ and $(x,y)$ stands for the GCD of $x$ and $y$.

Question

I need ideas on how to prove that if $a\equiv b\mod c$, then $(a,c)=(b,c)$, where $a$, $b$ and $c\in\mathbb{Z}$, $c>0$ and $(x,y)$ stands for the GCD of $x$ and $y$.

anonymous · Answer

b/a = c
b/c = a
if i remember correctly

cristiann · Answer

You should use the Euclid algorithm for finding GCD:
the GCD is last nonnull remainder of the procedure.
a=cq1+r, 0<= r <c
b=cq2+r [the same remainder, since they are equal mod c]
Now, for a the next division is c divided by r, and for b the same division ... they will lead to the same result.

anonymous · Answer

I managed to prove it in three or four lines.