Math 115. Slides from Lecture of September 20

This handout contains the slides from the lecture of September 20 (with minor corrections).

We’re interested in finding integers x that satisfy the system

x ≡ a_{1} (mod m_{1})
x ≡ a_{2} (mod m_{2})
…
x ≡ a_{r} (mod m_{r})

(*)

for given a_{1}, …, a_{r} ∈ ℤ.

Theorem (Chinese Remainder Theorem). Let a_{1}, …, a_{r} ∈ ℤ be given, and assume that m_{1}, …, m_{r} are pairwise relatively prime positive integers. Let m = m_{1} ⋯ m_{r}. Then the system (*) has solutions. Moreover, if x_{0} ∈ ℤ is one such solution, then x ∈ ℤ is a solution if and only if x ≡ x_{0} (mod m) .

Proof. We start with the partial proof from last time. Assume that r = 2 . Since gcd(m_{1}, m_{2}) = 1 , there are integers c_{1} and c_{2} such that c_{1}m_{1} + c_{2}m_{2} = 1 . Then

\begin{matrix}c_{1}m_{1} ≡ 0 (mod m_{1}) \\ c_{1}m_{1} ≡ 1 (mod m_{2}) \end{matrix}  and  \begin{matrix}c_{2}m_{2} ≡ 1 (mod m_{1}) \\ c_{2}m_{2} ≡ 0 (mod m_{2}) \end{matrix}

Let x_{0} = a_{1}c_{2}m_{2} + a_{2}c_{1}m_{1} . Then

x_{0} ≡ a_{1} · 1 + a_{2} · 0 = a_{1} (mod m_{1})  and
x_{0} ≡ a_{1} · 0 + a_{2} · 1 = a_{2} (mod m_{2}) ,

so it is a solution of (*).

Now let x ∈ ℤ. Then:

x is another solution ⟺ x ≡ a_{i} (mod m_{i}) for all i
⟺ x ≡ x_{0} (mod m_{i}) for all i
⟺ x ≡ x_{0} (mod m) .

This gives the last sentence.

The above is true for all r, but we still need to prove the main part for arbitrary r. This can be done by induction on r.

So, assume that r > 2 and that the theorem is true when r is replaced by r − 1 . By the inductive hypothesis there is an a_{0} such that a_{0} ≡ a_{i} (mod m_{i}) for all

i < r. By the r = 2 case there is an integer x_{0} such that x_{0} ≡ a_{0} (mod m_{1} ⋯ m_{r−1}) and x_{0} ≡ a_{r} (mod m_{r}) . This integer satisfies all parts of the system (*), because for all i < r we have

x_{0} ≡ a_{0} ≡ a_{i} (mod m_{i}) ,

and we still have x_{0} ≡ a_{r} (mod m_{r}) . □