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

[crypto_rsa]

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

If a \equiv r (mod m₁) and a \equiv r (mod m₂) then a \equiv r (mod [m₁, m₂]), where [a, b] is the least common multiple of a and b.

I have tried to prove that.

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

and

a = k_{1}m_{1} + r
a = k_{2}m_{2} + r

Then

al_{1} = k_{1}l_{1}m_{1} + rl_{1}
al_{2} = k_{2}l_{2}m_{2} + rl_{2}

thus

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

and

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

In order to

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

we have to prove that

(l_{1} - l_{2})\; | \; (k_{1} - k_{2})

But how?

 

[Gokul43201]

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) ... ?

 

[crypto_rsa]

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) ... ?

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 a \equiv r (mod [m1, m2])