Modular Mathematics, Chinese Remainder Theorem

Chinese Remainder Theorem

Given a set of values c₁ c₂ … c_n, and a set of mutually coprime moduli m₁ m₂ … m_n, is there an integer x such that x = c_i mod m_i 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 m₁, then x+w will not equal c₁ mod m₁, 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 a_i be the product of all the moduli other than m_i. Verify that a_i and m_i are coprime. Let b_i be the inverse of a_i mod m_i. Finally, let x be the sum of a_ib_ic_i 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.