Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

31.5 The Chinese remainder theorem

Around A.D. 100, the Chinese mathematician Sun-Tsu solved the problem of finding those integers x that leave remainders 2, 3, and 2 when divided by 3, 5, and 7 respectively. One such solution is x = 23; all solutions are of the form 23 + 105k for arbitrary integers k. The "Chinese remainder theorem" provides a correspondence between a system of equations modulo a set of pairwise relatively prime moduli (for example, 3, 5, and 7) and an equation modulo their product (for example, 105).

The Chinese remainder theorem has two major uses. Let the integer n be factored as n = n₁n₂ n_k, where the factors n_i are pairwise relatively prime. First, the Chinese remainder theorem is a descriptive "structure theorem" that describes the structure of Z_n as identical to that of the Cartesian product with componentwise addition and multiplication modulo n_i in the ith component. Second, this description can often be used to yield efficient algorithms, since working in each of the systems can be more efficient (in terms of bit operations) than working modulo n.

Theorem 31.27: (Chinese remainder theorem)

Let n = n₁n₂ n_k, where the n_i are pairwise relatively prime. Consider the correspondence

(31.23)

where a ∈ Z_n, , and

a_i = a mod n_i

for i = 1, 2, ..., k. Then, mapping (31.23) is a one-to-one correspondence (bijection) between Z_n and the Cartesian product . Operations performed on the elements of Z_n can be equivalently performed on the corresponding k-tuples by performing the operations independently in each coordinate position in the appropriate system. That is, if

a ↔ (a₁, a₂, ..., a_k),

b ↔ (b₁, b₂, ..., b_k),

then

(31.24)

(31.25)

(31.26)

Proof Transforming between the two representations is fairly straightforward. Going from a to (a₁, a₂, ..., a_k) is quite easy and requires only k divisions. Computing a from inputs (a₁, a₂, ..., a_k) is a bit more complicated, and is accomplished as follows. We begin by defining m_i = n/n_i for i = 1, 2, ..., k; thus m_i is the product of all of the n_j's other than n_i: m_i = n₁n₂ · · · n_i-1n_i+1 · · · n_k. We next define

(31.27)

for i = 1, 2, ..., k. Equation (31.27) is always well defined: since m_i and n_i are relatively prime (by Theorem 31.6), Corollary 31.26 guarantees that () exists. Finally, we can compute a as a function of a₁, a₂, ..., a_k as follows:

(31.28)

We now show that equation (31.28) ensures that a ≡ a_i (mod n_i) for i = 1, 2, ..., k. Note that if j ≠ i, then m_j ≡ 0 (mod n_i), which implies that c_j ≡ m_j ≡ 0 (mod n_i). Note also that c_i ≡ 1 (mod n_i), from equation (31.27). We thus have the appealing and useful correspondence

c_i ↔ (0, 0, ..., 0, 1, 0, ..., 0),

a vector that has 0's everywhere except in the ith coordinate, where it has a 1; the c_i thus form a "basis" for the representation, in a certain sense. For each i, therefore, we have

which is what we wished to show: our method of computing a from the a_i's produces a result a that satisfies the constraints a ≡ a_i (mod n_i) for i = 1, 2, ..., k. The correspondence is one-to-one, since we can transform in both directions. Finally, equations (31.24)-(31.26) follow directly from Exercise 31.1-6, since x mod n_i = (x mod n) mod n_i for any x and i = 1, 2, ..., k.

The following corollaries will be used later in this chapter.

Corollary 31.28

If n₁, n₂, ..., n_k are pairwise relatively prime and n = n₁n₂ n_k, then for any integers a₁, a₂, ..., a_k, the set of simultaneous equations

x ≡ a_i (mod n_i),

for i = 1, 2, ..., k, has a unique solution modulo n for the unknown x.

Corollary 31.29

If n₁, n₂, ..., n_k are pairwise relatively prime and n = n₁n₂ · · · n_k, then for all integers x and a,

x ≡ a (mod n_i)

for i = 1, 2, ..., k if and only if

x ≡ a (mod n).

As an example of the application of the Chinese remainder theorem, suppose we are given the two equations

so that a₁ = 2, n₁ = m₂ = 5, a₂ = 3, and n₂ = m₁ = 13, and we wish to compute a mod 65, since n = 65. Because 13^-1 ≡ 2 (mod 5) and 5^-1 ≡ 8 (mod 13), we have

and

See Figure 31.3 for an illustration of the Chinese remainder theorem, modulo 65.

Figure 31.3: An illustration of the Chinese remainder theorem for n₁ = 5 and n₂ = 13. For this example, c₁ = 26 and c₂ = 40. In row i, column j is shown the value of a, modulo 65, such that (a mod 5) = i and (a mod 13) = j. Note that row 0, column 0 contains a 0. Similarly, row 4,column 12 contains a 64 (equivalent to -1). Since c₁ = 26, moving down a row increases a by 26. Similarly, c₂ = 40 means that moving right by a column increases a by 40. Increasing a by 1 corresponds to moving diagonally downward and to the right, wrapping around from the bottom to the top and from the right to the left.

Thus, we can work modulo n by working modulo n directly or by working in the transformed representation using separate modulo n_i computations, as convenient. The computations are entirely equivalent.

Exercises 31.5-1

Find all solutions to the equations x ≡ 4 (mod 5) and x ≡ 5 (mod 11).

Exercises 31.5-2

Find all integers x that leave remainders 1, 2, 3 when divided by 9, 8, 7 respectively.

Exercises 31.5-3

Argue that, under the definitions of Theorem 31.27, if gcd(a, n) = 1, then

.

Exercises 31.5-4

Under the definitions of Theorem 31.27, prove that for any polynomial f, the number of roots of the equation f(x) ≡ 0 (mod n) is equal to the product of the number of roots of each of the equations f(x) ≡ 0 (mod n₁), f(x) ≡ 0 (mod n₂), ..., f(x) ≡ 0 (mod n_k).