if $a\cong b\pmod m$ prove $(a,m)=(b,m)$

Question

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

Answer 1

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

Answer 2

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

1. $d\mid x$ and $d\mid y$;
2. 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)$.