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

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

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

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:

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.

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.

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).

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

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

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

.

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).