(adsbygoogle = window.adsbygoogle || []).push({}); Why "modulo m1" and "modulo m2" implies "modulo [m1, m2]"

If [tex]a \equiv r[/tex] (mod m_{1}) and [tex]a \equiv r[/tex] (mod m_{2}) then [tex]a \equiv r[/tex] (mod [m_{1}, m_{2}]), 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]

and

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

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

Then

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

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

thus

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

and

[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?

**Physics Forums | Science Articles, Homework Help, Discussion**

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]

**Physics Forums | Science Articles, Homework Help, Discussion**