Number Theory: An Introduction to Mathematics

118 II Divisibility

Proposition 36 can be considerably generalized:

Proposition 37For any integers m 1 ,...,mnand a 1 ,...,an, the simultaneous con-
gruences

x≡a 1 modm 1 ,...,x≡anmodmn

have a solution x if and only if

aj≡akmod(mj,mk) for 1 ≤j<k≤n.

Moreover, y is also a solution if and only if

y≡xmod[m 1 ,...,mn].

proofThe necessity of the conditions is trivial. For ifxis a solution and ifdjk=
(mj,mk)is the greatest common divisor ofmjandmk,thenaj ≡x ≡akmoddjk.
Also, ifyis another solution, theny−xis divisible bym 1 ,...,mnand hence also by
their least common multiple [m 1 ,...,mn].
We prove the sufficiency of the conditions by induction onn. Suppose first that
n=2anda 1 ≡a 2 modd,whered=(m 1 ,m 2 ).BytheB ́ezout identity,

d=x 1 m 1 −x 2 m 2

for somex 1 ,x 2 ∈Z.Sincea 1 −a 2 =kdfor somek∈Z, it follows that

x:=a 1 −kx 1 m 1 =a 2 −kx 2 m 2

is a solution.
Suppose next thatn>2 and the result holds for all smaller values ofn. Then there
existsx′∈Zsuch that

x′≡aimodmi for 1≤i<n,

andx′is uniquely determined modm′,wherem′=[m 1 ,...,mn− 1 ]. Since any solu-
tion of the two congruences

x≡x′modm′,x≡anmodmn

is a solution of the given congruences, we need only show thatx′≡anmod(m′,mn).
But, by the distributive law connecting greatest common divisors and least common
multiples,

(m′,mn)=[(m 1 ,mn),...,(mn− 1 ,mn)].

Sincex′≡ai≡anmod(mi,mn)for 1≤i<n, it follows thatx′≡anmod(m′,mn).


Corollary 38Let m 1 ,...,mnbe integers, any two of which are relatively prime, and
let m=m 1 ···mnbe their product. Then, for any given integers a 1 ,...,an,thereisa
unique integer xmodm such that

x≡a 1 modm 1 ,...,x≡anmodmn.

Moreover, x is relatively prime to m if and only if aiis relatively prime to mifor
1 ≤i≤n.