# 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 $\displaystyle ra\equiv rb \ (\text{mod} \ m)$, then $\displaystyle a\equiv b \ \left(\text{mod} \ \frac{m}{gcd(r,m)}\right)$

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

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

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

$\displaystyle 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 $\displaystyle ra\equiv rb \ (\text{mod} \ m)$, then $\displaystyle a\equiv b \ \left(\text{mod} \ \frac{m}{gcd(r,m)}\right)$

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

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

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

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

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

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

From the given we can write:

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

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

$\displaystyle q(a-b)=kp$

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

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

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