Chinese Remainder Theorem: my notes on a 6 minute Ma Yuchun video.

The example in the Han Xin Counts Soldiers lesson is an example of the Chinese Remainder Theorem. Can we prove that such systems of congruence equations can always be solved?

Chinese Remainder Theorem. If m and n are relatively prime positive integers (relatively prime means that their only common divisor is 1) and if a, b, p, and q are non-negative integers such that a<m and b<n, then it is possible to find an x to satisfy the system of equations:

x=pm+a or x≡a (mod m)

x=qn+b or X≡b (mod n)

Proof. Consider the n integers a, m+a, 2m+a, …, (n-1)m+a. If we let k represent any of those n integers, k≡a (mod m). Consider the remainders of each k when diving by n. Assume that two of the n integers have the same remainder. Then for some 0≤ i,j ≤ n-1, im+a=qᵢn+r and jn+a=qⱼn+r. Subtracting these last two equations, we have (j-i)m=(qⱼ-qᵢ)n. That contradicts our assumption that m and n are relatively prime as they have the common divisors (j-i) and (qⱼ-qᵢ). So each k must have a distinct remainder. There are n such remainders. By the pigeonhole principle (see my notes on Ma Yuchun's introductory video on the topic), one of our k (which solve x=pm+a) must give a remainder b on division by n, that is, x=qn+b. In other words, the two equations are always solvable.

Generalized Chinese Remainder Theorem: if m₁, m₂, …, mₖ are k pairwise relatively prime positive integers (so gcd(mᵢ,mⱼ)=1 when i≠j, 1≤ i,j ≤k where gcd is the greatest common divisor function), then there is a solution x for the system of congruences equations:

x≡b₁ (mod m₁)
x≡b₂ (mod m₂)
⋮
x≡bₖ (mod mₖ).

From the free on-line course: Combinatorial Mathematics with Ma Yuchun of Tsinghua University

Lecture: Week 6, Inclusion-Exclusion Principle and Pigeonhole Principle, Pigeonhole Principle, Chinese Remainder Theorem