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])
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - modulo modulo implies Date
Using modulo 11 Sep 15, 2014
A big number modulo a prime Dec 12, 2012
Modulo and prime numbers Nov 4, 2012
Negative modulo question Jul 14, 2012
How to factor a polynomial modulo p? Feb 24, 2012