Chinese remainder theorem
A clever method appearted first in the bookd The Art of War, by Sun Tsu, in the 3rd century AD, allows one to deduce an integer from its approximate size and its least nonnegative remainder modulo m, for a few small m. One early application was to count soldiers. It is sufficient to request the soldiers to line up 5 abreast, then 8, then 19, and to count each time how many soldiers are not lined up: these remainders ri, for i = 1, 2 and 3, are smaller than 5, 8, and 19, respectively.
Theorem 4.23 (Chinese remainder theorem). Let r1, r2, ..., rn positive integers such that gcd(ri, rj) = 1 for all pairs (i, j) with i ≠ j. Then the systems of congruences
x ≡ c1 mod r1
x ≡ c2 mod r2 (4.6)
...
x ≡ c3 mod rs
admits a unique solution modulo R = r1 r2 ··· rs (any two solutions x and y are congruent modulo R).
Proof. Let Rk = R/rk; the hyphotesis gcd(ri, rj) = 1 implies that gcd(Rk, rk) = 1. So the k-th congruence
Rk x ≡ ck (mod rk)
admits as unique solution, x̄k, modulo rk (as stated in Proposition 4.18), the number
x̄ = R1 x̄1 + R2 x̄2 + ... + Rs x̄s
indeed as Ri is a multiple of rk for i ≠ k, we have
Ri ≡ 0 (mod rk) for i ≠ k
and so
x̄ ≡ R1x̄1 ≡ c1 mod r1
x̄ ≡ R2x̄2 ≡ c2 mod r2 (4.7)
...
x̄ ≡ R3x̄3 ≡ c3 mod rs
thus x̄ is a solution of the system.
As to the unicity modulo R, let ȳ be another solution of the system; in other words, assume that
x̄ ≡ ck ≡ ȳ (mod rk), for k = 1, ..., s.
so ȳ ≡ x̄ (mod rk) for each k. Thus rk | (x̄ − ȳ) for each k. But then, by Corollary 2.20, since the rk are pairwise relatively prime, rk | (x̄ − ȳ), and ȳ ≡ x̄ (mod R).□
Example 4.24. Solve the problem of counting a few hundred soldiers by linining them up by 7, 10 and 13. For each alignment we have the remainders r1 = 1, r2 = 3, and r3 = 8. Then we can set up the system
x ≡ 1 (mod 7);
x ≡ 3 (mod 10);
x ≡ 8 (mod 13).
By the Chinese remainder theorem, it admits a unique solution modulo R = 7 ⋅ 10 ⋅ 13 = 910. We have R1 = 10 ⋅ 13 = 130; R2 = 7 ⋅ 13 = 91; R3 = 7 ⋅ 10 = 70. Thus we need to solve the following congruences
The solution of the first congruence x = 2;
For the 2nd congruence first note that 91 ≡ 1 (mod 10), so 1 is the multiplicative inverse then x = 3.
For the 3rd congruence we notice that 5 ⋅ x ≡ 8 (mod 13), we find the multiplicative inverse of 5 mod 13: 5 ⋅ x ≡ 1 mod 13 which is 8 so by multiplying by 8 both sides we get 8 ⋅ 5 ⋅ x ≡ 8 ⋅ 8 (mod 13) since 8 · 5 ≡ 1 (mod 13), x = 8.
x̄ = 2⋅130 + 3⋅91 + 70⋅64 = 5013 ≡ 463 (mod 910)
Since there a few hundred soldiers, there must be exaclty 463 of them, as the next integer solution would be 463 + 910 = 1373.
Example 4.25 - Suppose, that lining up a group of pupils (< 1000) five abreast, one of them is not lined up, when eight abreast, 2 are not lined up, and when 19 abreast, 3 are not lined up. Then r1 = 1, r2 = 2 and r3 = 3. How many pupils are there?
Solution. In this case the number of the students is found by finding the solution, unique modulo R = 5 ⋅ 8 ⋅ 19 = 760, of the system
x ≡ 1 (mod 5),
x ≡ 2 (mod 8),
x ≡ 3 (mod 19).
We have R1 = 8 · 19 = 152, R2 = 5 · 19 = 95, R3 = 5 · 8 = 40; We need to find solutions for the system
152 ⋅ x ≡ 1 (mod 5)
95 ⋅ x ≡ 2 (mod 8)
40 ⋅ x ≡ 3 (mod 19)
The first congruence has x = 3 has solution. The second x = 6, so, the thirs x = 11; thus a solution is 3 · 152 + 6 · 95 + 11 · 40 = 1466 ≡ 706 mod 760. As 706 is the only solution smaller than 1000, this is the result we were looking for.
There is a useful consequence or, can also be seen as a different interpretation of the Chinese remainder theorem. Let ℤm× ℤn be the Cartesian product of ℤm and ℤn. As ℤr and ℤn are rings, the set ℤm × ℤn itself is in a natural way a product ring, in which the operations are defined by definition
(ām, b̄n) + ā'm, b̄'n) := (ām + c̄m, b̄n + b̄'n),
(ām, b̄n) · (ā'm, b̄'n) := (ām· c̄m, b̄n · b̄'n).
The following proposition is an immediate consequence of the Chinese remainder theorem.
Proposition 4.26. Let m and n be two relatively prime integers greater than 1. The map
f: ℤmn → ℤm × ℤn,
defined by
f(x̄mn) = (x̄m, ȳn),
is a bijection and it preserves the operations
f(x̄mn + ȳmn) = f(x̄mn) + f(ȳmn),
f(x̄mn · ȳmn) = f(x̄mn) · f(ȳmn),
Proof. We deed to check trhree things: 1) f is well-defined 2) f is injective; 3) f is surjective.
We first need to check f is well defined; i.e. a ≡ b mod mn, then f(a mod mn) = f(b mod mn). Indeed, suppose that a ≡ b mod mn. Then mn divides a − b, and therefore m and n are divisors of a - b. This shows that a ≡ b mod m and a ≡ b mod n. hence
f(a mod mn) = (a mod m, mod n) = (b mod m, b mod n) = f(b mod mn)
Now we show that f is injective; i.e., f(a mod mn) = f(b mon mn) implies that a ≡ b mod mn. Indeed, if f(a mon mn) = f(b mod mn), then
(a mod m, mod n) = (b mod m, b mod n)
In particular a and b are solutions to the system
x ≡ a (mod m),
x ≡ a (mod n)
However since gcd(m,n) = 1, the chinese remainder theorem gurantess that there is a unique solution to this system modulo mn. Hence, we must have a ≡ b mod mn as claimed. This proves f is injective.
It remains to show the surjectivty of f, i.e., for all (u mod m, v mod n) ∈ ℤm × ℤn there is some a mod mn, such that f(a mod mn) = (u mod m, v mod n). In order to show this, let (u mod m, v mod n) be an arbitrary element of the direct product ℤm × ℤn. Since gcd(m,n) = 1, the Chinese remainder theorem implies that the system
x ≡ u (mod m),
x ≡ v (mod n)
has a unique solution x0 mod mn such that x0 ≡ u mod m and x0 ≡ v mod n. Hence,
f(x0 mod mn) = (x0 mod m, x0 mod n) = (u mod m, v mod n)
and this shows that f is surjective.
Therefore f is a bijections. This ends the proof of the theorem.□