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.
