The following theorem is known as the Chinese remainder theorem because it was discovered by Qin Jiushao (1202 - 1261).
Let $m_1,m_2,\ldots,m_r$ be positive integers and let $a_1,\ldots,a_r$ be any integers. The simultaneous congruences $$\begin{array}{rcl} x(m_1)&\equiv&a_1(m_1)\\ x(m_2)&\equiv&a_2(m_2)\\ &\vdots&\\ x(m_r)&\equiv& a_r(m_r)\\ \end{array}\label{eq:E18594}\tag{*}$$ have a solution if and only if for all pairs of numbers $a_i,a_j$ with $i\neq j$ the greatest common divisor $d:=\gcd(a_i,a_j)$ is a divisor of $a_i-a_j$ (equivalently $a_i\equiv a_j\mod \gcd(a_i,a_j)$ whenever $i\neq j$).
In this case, the solution consists of all integers belonging to a single congruence class modulo $m=\operatorname{lcm}(m_1,m_2,\cdots, m_r),$ where $m$ is the least common multiple of the $r$ numbers $m_1,\ldots,m_r.$
In particular, $(\ref{eq:E18594})$ is always solvable if $m_i\perp m_j$ are co-prime, whenever $i\neq j.$
Proofs: 1
