if $a\cong b\pmod m$ prove $(a,m)=(b,m)$ This question gives one info which is $a\cong b \pmod m$ then we have to conclude that $(a,m)=(b,m)$. 
Here is what I have so far 
$a \cong b \pmod m$ so $a-b=mj$ so $a=mj+b$ , $b=a-mj$ 
also let $(a,m)=d_1$ and $(b,m)=d_2$ so 
$ax+my=d_1c$ and $au+mv=d_2k$ 
I did some algebra and got 
$$m(jx+y-uj)+bx+au=d_2k+d_1c$$
I am stuck here....
Any hints will be greatly useful 
 A: $a = b+mj $ 
Let $d1=\gcd (a,m) $ and $d2=\gcd (b,m)$.
$d1$ divides $m$. And $d1$ divides $a$.  So $d1$ divides $a - mj =b$.  So $d1$ divides $b$.  And as $d1$ divides $m$ we know $d1$ is a common divisor of $b$ and $m$.  Now $d2$ is the GREATEST common divisor of $b$ and $m$ so by definition $d2 \ge d1$.
Likewise $d2 $ divides $b+mj=a $ and so $d2$ is a common divisor of $a $ and $m $.  So $d1 \ge d2$.
So $d1=d2$.
A: It's easy if you use the following characterization of the greatest common divisor.

$d\ge 0$ is the greatest common divisor of the integers $x$ and $y$ if and only if

*

*$d\mid x$ and $d\mid y$;

*for every integer $e\ge0$, if $e\mid x$ and $e\mid y$, then $e\mid d$.


This has the advantage that no hypothesis whether $x$ and $y$ are zero is necessary.
Let $d=\gcd(a,m)$ and write $b=a+mk$. Then $d\mid a$ and $d\mid m$, so clearly $d\mid(a+mk)$, hence $d\mid b$.
Suppose $e\mid b$ and $e\mid m$. Then $e\mid a$, because $a=b-mk$. Therefore $e\mid d$, by the fact $d=\gcd(a,m)$.
Hence $d=\gcd(b,m)$.
