= Solution
For pairwise <coprime integers> $m_1,\ldots,m_r$, put $M=\prod_i m_i$. The <Chinese remainder theorem> states that reduction gives an isomorphism
$$
\mathbb Z/M\mathbb Z\longrightarrow\prod_{i=1}^r\mathbb Z/m_i\mathbb Z.
$$
Equivalently, every system $x\equiv a_i\pmod {m_i}$ has one solution modulo $M$.
For existence, let $M_i=M/m_i$. Since $\gcd(M_i,m_i)=1$, choose $u_i$ with $u_iM_i\equiv1\pmod {m_i}$. Then
$$
x=\sum_{i=1}^r a_i u_iM_i
$$
has every required residue: modulo $m_j$, all terms except the $j$th vanish and the remaining term is $a_j$. For uniqueness, if $x$ and $y$ have the same residues, every $m_i$ divides $x-y$. Pairwise coprimality then makes $M$ divide $x-y$. \b[Thus the simultaneous solution exists and is unique modulo $M$.]
Back to article page
