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 Motion, Modular transformation and Secret Sharing by CRT.