Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why modulo m1 and modulo m2 implies modulo [m1, m2]

  1. Sep 17, 2010 #1
    Why "modulo m1" and "modulo m2" implies "modulo [m1, m2]"

    If [tex]a \equiv r[/tex] (mod m1) and [tex]a \equiv r[/tex] (mod m2) then [tex]a \equiv r[/tex] (mod [m1, m2]), where [a, b] is the least common multiple of a and b.

    I have tried to prove that.

    Assume that
    [tex][m_{1}, m_{2}] = l_{1}m_{1} = l_{2}m_{2}[/tex]


    [tex]a = k_{1}m_{1} + r[/tex]
    [tex]a = k_{2}m_{2} + r[/tex]


    [tex]al_{1} = k_{1}l_{1}m_{1} + rl_{1}[/tex]
    [tex]al_{2} = k_{2}l_{2}m_{2} + rl_{2}[/tex]


    [tex]a(l_{1} - l_{2}) = [m_{1}, m_{2}](k_{1} - k_{2}) + r(l_{1} - l_{2})[/tex]


    [tex]a = [m_{1}, m_{2}] {(k_{1} - k_{2}) \over (l_{1} - l_{2})} + r[/tex]

    In order to

    [tex]a \equiv r\ (mod [m_{1}, m_{2}])[/tex], or [tex]a = K[m_{1}, m_{2}] + r[/tex]

    we have to prove that

    [tex](l_{1} - l_{2})\; | \; (k_{1} - k_{2})[/tex]

    But how?
  2. jcsd
  3. Sep 17, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: Why "modulo m1" and "modulo m2" implies "modulo [m1, m2]"

    This doesn't directly answer your question, but wouldn't the proof be a lot easier if you started off with m1|(a-r) and m2|(a-r) ... ?
  4. Jan 3, 2011 #3
    Re: Why "modulo m1" and "modulo m2" implies "modulo [m1, m2]"

    You are right, the proof is actually very simple:

    If m1 | (a-r) and m2 | (a-r) then a-r is a common multiple of m1 and m2. Therefore it is divisible by the least common multiple, [m1, m2]. Thus [m1, m2] | (a-r), or [tex]a[/tex] [tex] \equiv r[/tex] (mod [m1, m2])
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook