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])