Results 1 to 2 of 2

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

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10

    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)?
    Last edited by dwsmith; Jun 15th 2011 at 07:52 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

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

    Quote Originally Posted by dwsmith View Post
    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})$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Let p be odd. Then 2(p-3)!\equiv -1 (mod p)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jul 12th 2010, 03:42 PM
  2. Replies: 2
    Last Post: Jul 10th 2010, 05:14 PM
  3. [SOLVED] 2n^3+3n^2+n\equiv 0 (mod 6)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jul 8th 2010, 11:44 PM
  4. [SOLVED] if ab\equiv 0 (mod p), then a\equiv 0 (mod p) or b\equiv 0 (mod p).
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jul 7th 2010, 04:21 PM
  5. [SOLVED] if a^2 \equiv 1, then a \equiv \pm 1 (mod p)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jun 27th 2010, 03:43 PM

/mathhelpforum @mathhelpforum