Chinese Remainder Theorem

Let and be positive integers which are relatively prime and let and be any two integers. Then there is an integer such that

(1)

and

(2)

Moreover, is uniquely determined modulo . An equivalent statement is that if , then every pair of residue classes modulo and corresponds to a simple residue class modulo .

The Chinese remainder theorem is implemented in the Wolfram Language as ChineseRemainder[a1, a2, ...m1, m2, ...]. The Chinese remainder theorem is also implemented indirectly using Reduce in with a domain specification of Integers.

The theorem can also be generalized as follows. Given a set of simultaneous congruences

(3)

for , ..., and for which the are pairwise relatively prime, the solution of the set of congruences is

(4)

where

(5)

and the are determined from

(6)

Wolfram Web Resources