Theorem 2.6 (Chinese remainder theorem). Let (n.), be a pairwise relatively prime family of positive integers, and let a.....ak be arbitrary integers. Then there exists a solution a € Z to the system of congruences a = a, (mod n) (i = 1,...,k). Moreover, any de Z is a solution to this system of congruences if and only if a=d' (mod n), where n := [In Proof. To prove the existence of a solution a to the system of congruences, we first show how to construct integers e..... ex such that for i, j = 1,..... k, we have = { 1 (mod n,) if j=i. If we do this, then setting a= - Σ aje. i=] (2.6) one sees that for j = 1,..., k, we have a= Σa,e,a, (mod n,). since all the terms in this sum are zero modulo n,, except for the term i = j, which is congruent to a, modulo nj. To construct ej..... ek satisfying (2.6), let n = II, as in the statement of the theorem, and for i = 1,...,k, let n = n/n,; that is, n is the product of all the moduli n, with ji. From the fact that (n,) is pairwise relatively prime. it follows that for i = 1,....k, we have gcd (m, n) = 1, and so we may define nt. One sees that e, 0 (mod n,). Thus, (2.6) is satisfied. 1, (n) mod n, and e, we have n, n, and so e, 1 (mod n,), while for j i. That proves the existence of a solution a to the given system of congruences. If a=d' (mod n), then since n, | n for i = 1,..., k, we see that d² = a = a, (mod n,) for i=1,....k, and so d' also solves the system of congruences. Finally, if d' is a solution to the given system of congruences, then a = a, = d' (mod n,) for i = 1,...,k. Thus, n, | (a-d) for i = 1,.... k. Since (n,) is pairwise relatively prime, this implies n | (a-d'), or equivalently, ad' (modn).