Chinese Remainder Theorem (CRT)

The original form of the theorem, found in a book of  the Chinese mathematician Sun Zi published in 100-300 a.c., is a statement about simultaneous congruences.

Chinese Remainder Theorem

Suppose m1, m2, ... , mt are positive integers which are pairwise coprime and a1, a2, ... , at any given integers (ai < mi, i = 1, ..., t).

Then exists an integer x solving the system of simultaneous congruences

                                         x a1 mod m1

                                         x a2 mod m2

                                         :

                                         x at mod mt

which is unique  mod M with M = m1 ∙ m2 ∙ … ∙ mt.  

Furthermore, all solutions x + k ∙ M (k in Z) to this system are congruent modulo the product M.

A solution x can be found as follows:

For each i, the integers mi und Mi := M / mi are coprime, and using the extended Euclidean algorithm we can find integers r and s such that

r ∙ mi + s ∙ Mi = 1

is a representation of the greatest common divisor (gcd) of mi and Mi.

s is the modular inverse from Mi mod mi (s = Mi -1 mod mi).

If we set ei := s ∙ Mi, then we have

ei 1 mod mi

ei 0 mod mj, j ≠ i

and the integers e1,..., et are called base.

The solution to the system of simultaneous congruences is therefore x := a1e1+a2e2 +...+ atet.

Example

We consider the problem of finding an integer x such that

x 2 mod 3

x 3 mod 5

x 2 mod 7

We get M = 3 · 5 · 7 = 105,

M1 = M/3 = 35,

M2 = M/5 = 21,

M3 = M/7 = 15.

Using the extended Euclidean algorithm we find integers r and s, so that  mi · r + Mi · s = 1 or respectively

     r · mi + s · Mi   = 1:

(-23) · 3 + 2 · 35 = 1, also e1 = s · M1 =70       

  (-4) · 5 + 1 · 21 = 1, also e2 = s · M2 = 21

  (-2) · 7 + 1 · 15 = 1, also e3 = s · M3 = 15

A solution x is therefore  x = 2 · 70 + 3 · 21 + 2 · 15 = 233.

All other solutions are congruent to 233 23 mod 105, which means that they are all congruent to 23 mod 105.

A practical demonstration of  Chinese Remainder Theorem (CRT) is shown in the Applications of the Chinese Remainder Theorem (CRT) related to the 3 topics Astronomy and planetary MotionModular transformation and Secret Sharing by CRT.