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

1. Sep 17, 2010

### crypto_rsa

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

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

2. Sep 17, 2010

### Gokul43201

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

3. Jan 3, 2011

### crypto_rsa

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

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook