Modular Mathematics, Chinese Remainder Theorem

Chinese Remainder Theorem

Given a set of values c1 c2 … cn, and a set of mutually coprime moduli m1 m2 … mn, is there an integer x such that x = ci mod mi for each i in 1 through n?

Let z be the product of all the moduli. If x is a solution then so is x plus any multiple of z. If w is not a multiple of z, say w is not divisible by m1, then x+w will not equal c1 mod m1, and x+w will not be a solution. The solution, if it exists, is well defined mod z.

To show that a solution exists, we simply construct one. Let ai be the product of all the moduli other than mi. Verify that ai and mi are coprime. Let bi be the inverse of ai mod mi. Finally, let x be the sum of aibici for all i in 1 … n. Verify that x satisfies all n equations simultaneously.

If the original moduli are not coprime, split each equation up into a set of equations by factoring the composite modulus into prime powers. Then consider all the equations together. Equations sharing a common prime modulus are either redundant or inconsistent. An inconsistent example is x = 4 mod 6 and x = 11 mod 15. This would force x = 1 mod 3 and x = 2 mod 3, which is impossible. The example x = 4 mod 6 and x = 7 mod 15 has the solution x = 22 mod 30.