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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.