Multi-Page Printing

10 1. Preliminary Notions 1.7. The Chinese Remainder Theorem The following theorem is very important in number theory. Theorem 1.12. (Chinese Remainder Theorem) Let m1, . . . , mk be positive integers with (mi,mj) = 1 for all 1 ≤ i j ≤ k. Let a1,...,ak be arbitrary integers. Then there is an integer a such that (1.9) a ≡ ai (mod mi) for all i = 1,...,k. Proof. Let M = k i=1 mi and Mi = M/mi for i = 1,...,k. Since (mi,mj) = 1 whenever i = j, we get that mi and Mi are coprime for i = 1,...,k. In particular, the class Mi (mod mi) is invertible modulo mi. Let ni be an integer such that niMi ≡ 1 (mod mi). Put (1.10) a = k i=1 ainiMi. One easily checks that the positive integer a given in (1.10) satisfies (1.9). To see this, let be any index in {1,...,k}. Since m | Mj for j = , we get that a ≡ k i=1 ainiMi ≡ a n M ≡ a (mod m ), implying that a satisfies (1.9). Corollary 1.13. Let m1, . . . , mk be positive integers with (mi,mj) = 1 for all 1 ≤ i j ≤ k. The map (1.11) ψ : Z/(m1 · · · mk)Z −→ Z/m1Z × · · · × Z/mkZ given by a (mod m1 · · · mk) −→ (a (mod m1),..., a (mod mk)) is a ring isomorphism. Proof. One easily checks that ψ is a morphism of rings. To see that ψ is injective, let a be an integer such that ψ(a (mod m1 · · · mk)) = 0. In particular, a ≡ 0 (mod mi) for each i = 1,...,k, so that mi | a for all i = 1,...,k. Since (mi,mj) = 1 for i = j, we conclude that m1 · · · mk | a, so that a ≡ 0 (mod m1 · · · mk). The fact that ψ is surjective is then an immediate consequence of the Chinese Remainder Theorem.