- #1
crypto_rsa
- 4
- 0
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]
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?
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]
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?