TAOCP 4.3.2 Exercise 3
Let m=\operatorname{lcm}(m_1,m_2,\ldots,m_r).
Section 4.3.2: Modular Arithmetic
Exercise 3. ▶ [M26] (Generalized Chinese Remainder Theorem.) Let $m_1, m_2, \ldots, m_r$ be positive integers. Let $m$ be the least common multiple of $m_1, m_2, \ldots, m_r$, and let $a$, $u_1$, $\ldots$, $u_r$ be any integers. Prove that there is exactly one integer $u$ that satisfies the conditions
$$a \le u < a + m, \qquad u \equiv u_j \pmod{m_j}, \quad 1 \le j \le r,$$
provided that
$$u_i \equiv u_j \pmod{\gcd(m_i, m_j)}, \qquad 1 \le i < j \le r;$$
and there is no such integer $u$ when the latter condition fails to hold.
Verified: yes
Solve time: 9m
Solution
Let
$$ m=\operatorname{lcm}(m_1,m_2,\ldots,m_r). $$
We must prove that the system
$$ u\equiv u_j \pmod{m_j},\qquad 1\le j\le r, $$
has a solution if and only if
$$ u_i\equiv u_j \pmod{\gcd(m_i,m_j)}, \qquad 1\le i<j\le r, $$
and that in the solvable case there is exactly one solution $u$ satisfying
$$ a\le u<a+m. $$
Necessity
Assume that an integer $u$ satisfies
$$ u\equiv u_j \pmod{m_j},\qquad 1\le j\le r. $$
Fix $i<j$. Then
$$ u-u_i\equiv0\pmod{m_i}, \qquad u-u_j\equiv0\pmod{m_j}. $$
Subtracting,
$$ u_i-u_j=(u_i-u)+(u-u_j). $$
Since $\gcd(m_i,m_j)$ divides both $m_i$ and $m_j$, it divides each summand on the right-hand side; hence
$$ u_i-u_j\equiv0\pmod{\gcd(m_i,m_j)}. $$
Therefore
$$ u_i\equiv u_j\pmod{\gcd(m_i,m_j)} $$
for all $i<j$. Thus the compatibility condition is necessary.
Sufficiency
Assume now that
$$ u_i\equiv u_j\pmod{\gcd(m_i,m_j)} \qquad (1\le i<j\le r). $$
We prove by induction on $r$ that the system is solvable.
Base case: $r=2$
Let
$$ d=\gcd(m_1,m_2), \qquad m_1=d m_1', \qquad m_2=d m_2', $$
with $\gcd(m_1',m_2')=1$.
Since $u_1\equiv u_2\pmod d$, write
$$ u_1-u_2=d,t. $$
A solution of
$$ u\equiv u_1\pmod{m_1} $$
has the form
$$ u=u_1+d m_1' k. $$
Substituting into the second congruence gives
$$ u_1+d m_1'k\equiv u_2\pmod{d m_2'}, $$
hence
$$ d m_1'k\equiv u_2-u_1=-dt \pmod{d m_2'}. $$
Dividing by $d$,
$$ m_1'k\equiv -t\pmod{m_2'}. $$
Since $\gcd(m_1',m_2')=1$, this congruence has a solution $k$, unique modulo $m_2'$. Therefore a solution $u$ exists, and all solutions are congruent modulo
$$ d,m_1'm_2' = \operatorname{lcm}(m_1,m_2). $$
Thus the theorem holds for two moduli.
Inductive step
Assume the theorem true for $r-1$ moduli.
Let
$$ M=\operatorname{lcm}(m_1,\ldots,m_{r-1}). $$
By the induction hypothesis, there exists an integer $v$ satisfying
$$ v\equiv u_j\pmod{m_j}, \qquad 1\le j\le r-1. $$
To combine $v$ with the congruence
$$ u\equiv u_r\pmod{m_r}, $$
we must verify the compatibility condition for the two moduli $M$ and $m_r$.
For each $j<r$,
$$ v\equiv u_j\pmod{m_j}, $$
and by hypothesis,
$$ u_j\equiv u_r\pmod{\gcd(m_j,m_r)}. $$
Hence
$$ v-u_r $$
is divisible by $\gcd(m_j,m_r)$ for every $j<r$.
Now
$$ \gcd(M,m_r) = \operatorname{lcm}!\bigl( \gcd(m_1,m_r),\ldots,\gcd(m_{r-1},m_r) \bigr). $$
Therefore $v-u_r$ is divisible by each $\gcd(m_j,m_r)$, hence by their least common multiple:
$$ v-u_r\equiv0\pmod{\gcd(M,m_r)}. $$
Thus
$$ v\equiv u_r\pmod{\gcd(M,m_r)}. $$
By the two-modulus case, there exists an integer $u$ satisfying
$$ u\equiv v\pmod M, \qquad u\equiv u_r\pmod{m_r}. $$
Since every $m_j$ with $j<r$ divides $M$, the first congruence implies
$$ u\equiv v\equiv u_j\pmod{m_j} \qquad (1\le j<r). $$
Together with
$$ u\equiv u_r\pmod{m_r}, $$
this yields
$$ u\equiv u_j\pmod{m_j} \qquad (1\le j\le r). $$
Hence the system is solvable for $r$ moduli. The induction is complete.
Uniqueness modulo $m$
Suppose $u$ and $u'$ both satisfy
$$ u\equiv u_j\equiv u' \pmod{m_j}, \qquad 1\le j\le r. $$
Then $u-u'$ is divisible by every $m_j$. Therefore $u-u'$ is divisible by their least common multiple:
$$ u-u'\equiv0\pmod m. $$
Hence all solutions are congruent modulo $m$.
Unique representative in $[a,a+m)$
Every residue class modulo $m$ contains exactly one integer in the interval
$$ [a,a+m). $$
Since the solution set is a single residue class modulo $m$, there is exactly one solution $u$ satisfying
$$ a\le u<a+m. $$
Failure of the compatibility condition
If for some $i<j$,
$$ u_i\not\equiv u_j\pmod{\gcd(m_i,m_j)}, $$
then any common solution $u$ would imply
$$ u_i\equiv u\equiv u_j \pmod{\gcd(m_i,m_j)}, $$
contradicting the assumption.
Therefore no solution can exist.
Hence there exists exactly one integer $u$ with
$$ a\le u<a+m, \qquad u\equiv u_j\pmod{m_j} \quad (1\le j\le r), $$
if and only if
$$ u_i\equiv u_j\pmod{\gcd(m_i,m_j)} \qquad (1\le i<j\le r). $$
If this compatibility condition fails, no such integer exists. ∎