## anonymous 4 years ago 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$$.

1. anonymous

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

2. cristiann

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.

3. anonymous

I managed to prove it in three or four lines.