= Solution
The <Chinese remainder theorem> says that if the positive integers $m_1,\ldots,m_r$ are pairwise <coprime integers>[coprime] and $M=\prod_i m_i$, then for arbitrary residue classes $a_i\pmod{m_i}$ there is a unique residue class $x\pmod M$ satisfying
$$
x\equiv a_i\pmod{m_i}
\qquad(1\leq i\leq r).
$$
Equivalently, reduction is a <ring isomorphism>
$$
\mathbb Z/M\mathbb Z\longrightarrow
\prod_{i=1}^r\mathbb Z/m_i\mathbb Z.
$$
For existence, put $M_i=M/m_i$. Pairwise coprimality gives $\gcd(M_i,m_i)=1$, so <Bezout identity>[Bézout's identity] supplies an integer $u_i$ with $u_iM_i\equiv1\pmod{m_i}$. Then
$$
x=\sum_{i=1}^r a_i u_iM_i
$$
has the required residues, because every term except the $i$th is divisible by $m_i$. If $x$ and $y$ are two solutions, each $m_i$ divides $x-y$. Pairwise coprimality then implies that their product $M$ divides $x-y$, proving uniqueness modulo $M$.
Back to article page
