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.