When a congruence system can be solved?

Solution 1:

Hint $\ $ Suppose for induction there is a solution $\,x = a\,$ to the first $\,n\!-\!1\,$ congruences, i.e.

$$a\equiv a_i\!\!\pmod{m_i},\,\ i=1,\ldots n-1\tag{#}$$

Combining the solution with the final congruence we obtain the system

$$\begin{align} &x \equiv a\! \pmod m,\ \ m = {\rm lcm}(m_1,\ldots m_{n-1})\\ &x\equiv a_n\!\!\!\! \pmod{m_n}\end{align}$$

We know this is solvable iff $\,(m_n,m)\mid a-a_n.\ $ Since gcd distributes over lcm we have

$$(m_n,m) = (m_n,{\rm lcm}(m_1,\ldots m_{n-1}) = {\rm lcm}((m_n,m_1),\ldots,(m_n,m_{n-1})) =: \ell $$

Hence $\ (m_n,m)\mid a-a_n \iff \ell\mid a-a_n\iff (m_n,m_i)\mid a-a_n,\ $ for all $\,i \le n-1$

$\ \ (m_n,m_i)\mid m_i\mid a-a_i\,$ since $\,a\,$ is a solution of the first $\,n-1\,$ congruences $\,({\#})$

$\qquad\ \ (m_n,m_i)\mid a_n\!-\!a_i\,$ by hypothesis. Therefore it divides their difference, i.e.

$\qquad\ \ (m_n,m_i)\mid a-a_n = a-a_i -(a_n - a_i).\ $ Therefore a solution exists.

Remark $\ $ Domains satsifying CRT = Chinese Remainder Theorem are known as Prüfer domains. They are non-Noetherian generalizations of Dedekind domains. Their ubiquity stems from a remarkable confluence of interesting characterizations. See this answer for a couple dozen characterizatons.