Results 1 to 6 of 6

Math Help - more gcd

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    11

    more gcd

    I am stuck on this one too........let m,n be integers such that gcd(m,n)=1. prove that if a equivalent to b mod m and a equivalent to b mod n, then a equivalent to b mod (mn)

    thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Since a \equiv b \mod m, we have m \mid (a-b). Similarily n \mid (a-b). Now you probably know that if s \mid u, t \mid u and (s,t)=1 then st \mid u. What do you conclude?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    11

    ?

    Quote Originally Posted by Bruno J. View Post
    Since a \equiv b \mod m, we have m \mid (a-b). Similarily n \mid (a-b). Now you probably know that if s \mid u, t \mid u and (s,t)=1 then st \mid u. What do you conclude?
    do you conclude that a is equivalent to b mod (mn)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Ultimately, yes. But do you understand why?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2010
    Posts
    11
    Quote Originally Posted by Bruno J. View Post
    Ultimately, yes. But do you understand why?
    is it because s and t both divide u therefore mn divides a and b
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Yes!
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum