# systems of congruences

Printable View

• October 6th 2009, 05:58 PM
ilikecandy
systems of congruences
Hello. I am completely stumped by this problem:

x = a1 (mod m1)
x = a2 (mod m2)
...
x = an (mod mn)

Let mj be arbitrary positive integers. Show that there is a simultaneous solution of this system if and only if ai= aj (mod(mi, mj)) for all pairs of the indices i,j for which 1 <= i < j <= r

Thanks for the help.
• October 7th 2009, 02:43 PM
HallsofIvy
What do you mean by "mod(mi,mj)"?
• October 7th 2009, 04:54 PM
ilikecandy
I mean the greatest common divisor of mi and mj as the modulo. mi is $m_{i}$ and mj is $m_{j}$
• October 7th 2009, 09:07 PM
aidan
This in the commonly known Chinese Remainder Theorem.
Use Google to get some explanations.
There are proofs available on the internet.