# Thread: if ra\equiv rb (mod m), then a\equiv b (mod \frac{m}{gcd(r,m)})

1. ## if ra\equiv rb (mod m), then a\equiv b (mod \frac{m}{gcd(r,m)})

if $ra\equiv rb \ (\text{mod} \ m)$, then $a\equiv b \ \left(\text{mod} \ \frac{m}{gcd(r,m)}\right)$

Let $d=gcd(r,m)$
Then $d|r \ \text{and} \ d|m$

$\Rightarrow ds=r \ \text{and} \ dt=m, \ \ st,\in\mathbb{Z}$

$t=\frac{m}{gcd(r,m)}$

$m|[r(a-b)]\Rightarrow t|[r(a-b)]$

How can show t and r are coprime so t|(a-b)?

2. ## Re: if ra\equiv rb (mod m), then a\equiv b (mod \frac{m}{gcd(r,m)})

Originally Posted by dwsmith
if $ra\equiv rb \ (\text{mod} \ m)$, then $a\equiv b \ \left(\text{mod} \ \frac{m}{gcd(r,m)}\right)$

Let $d=gcd(r,m)$
Then $d|r \ \text{and} \ d|m$

$\Rightarrow ds=r \ \text{and} \ dt=m, \ \ st,\in\mathbb{Z}$

$t=\frac{m}{gcd(r,m)}$

$m|[r(a-b)]\Rightarrow t|[r(a-b)]$

How can show t and r are coprime so t|(a-b)?

$d=gcs(r,m)$
$ra\equiv rb(\mod m)$
-----------------
$d=gcd(r,m)$

From the given we can write:

(1) $r(a-b)=ra-rb=lm$, for $k\in\mathbb{Z}$.

d=gcd(r,m), therefor there are exist $p,q$ co-prime. so that: $m=dp$, $r=dq$, we put these in (1), and we will get:

$q(a-b)=kp$

Hence, $p|q(a-b)$ and $gcd (p,q)=1$.

Recalling the Euclid's lemma we will get: $p|(a-b)$or $a\equiv b(\mod p)$ or:

$a\equiv b(\mod \frac{m}{d})$