Chinese remainder theorem The system is X=a mod m1 X a, mod m X-a mod m Assume that g.c.d. (mi, mi )=1 for i+. The system has a unique solution modulo M=m m2Chinese Remainder Theorem • The system is – x = a1 mod m1 – x = a2 mod m2 – …. – x = ar mod mr – Assume that g.c.d.(mi , mj ) = 1 for i j. The system has a unique solution modulo M=m1m2…mr