Exercise 2.3.19 (Solvability of $b_i x \equiv a_i \pmod{m_i},\ i=1,\ldots,r$)

Proof. Write $d_i=m_i\wedge a_i$ the gcd of $m_i$ and $a_i$. The congruence $b_{i}x\equiv a_i(\mathit{mod}{m}_i)$ is solvable if and only if $d_i\mid b_i$. Denotes $a_i^{\prime }=a_i∕d_i,b_i^{\prime }=b_i∕d_i,m_i^{\prime }=m_i∕d_i$. then

Now $b_i^{\prime }\wedge m_i^{\prime }=1$, thus there exists an inverse $c_i$ of $b_i^{\prime }$ modulo $m_i^{\prime }$, i.e. $c_i{b}_i^{\prime }\equiv 1(\mathit{mod}{m}_i^{\prime })$.

Then

$b_i^{\prime }x\equiv a_i^{\prime }(\mathit{mod}{m}_i^{\prime })⟺x\equiv c_i{a}_i^{\prime }(mod{m}_i^{\prime }),i=1,2,\dots ,r.$

Since $m_i^{\prime }\mid m_i$ for all $i$, $m_1^{\prime },m_2^{\prime },\dots ,m_r^{\prime }$ are relatively prime by pairs. The Chinese Remainder Theorem shows that the system

is solvable. So is the equivalent system $b_{i}x\equiv a_i(\mathit{mod}{m}_i),i=1,2,\dots ,r$. □