This note introduces the Chinese Remainder Theorem and outlines a standard proof.
Statement
We begin with congruences: if two integers $a$ and $b$ leave the same remainder when divided by a positive integer $m$, then we write
$$ a \equiv b \pmod m $$
A system of congruences is simply a collection of such relations.
We also need the notion of a modular inverse. For integers $a$ and $m$, if there exists an integer $b$ such that
$$ a \times b \equiv 1 \pmod m $$
then $b$ is called the modular inverse of $a$ modulo $m$. Such an inverse exists only when $a$ and $m$ are coprime.
The Chinese Remainder Theorem states that for a system
$$ S=\begin{cases} x \equiv a_1 \pmod{m_1}\ x \equiv a_2 \pmod{m_2}\ \dots\ x \equiv a_n \pmod{m_n} \end{cases} $$
if the moduli $m_i$ are pairwise coprime, then the system always has a solution for arbitrary integers $a_i$, and the general solution can be written as
$$ x=kM + \sum_{i=1}^{n}a_it_iM_i $$
where $k \in \mathbb{Z}$, $M=\prod_{i=1}^n m_i$, $M_i=M/m_i$, and $t_i$ is the modular inverse of $M_i$ modulo $m_i$.
Proof sketch
For each pair $i \neq j$, pairwise coprimality implies that $m_i$ and $M_i$ are coprime. Hence there exists $t_i$ such that
$$ t_iM_i \equiv 1 \pmod{m_i} $$
Therefore
$$ a_it_iM_i \equiv a_i \pmod{m_i} $$
while for $j \neq i$,
$$ a_jt_jM_j \equiv 0 \pmod{m_i} $$
This shows that
$$ x=\sum_{i=1}^{n}a_it_iM_i $$
satisfies every congruence in the system.
If $x_1$ and $x_2$ are two solutions, then $x_1-x_2 \equiv 0 \pmod{m_i}$ for every $i$. Since the $m_i$ are pairwise coprime, their product $M$ divides $x_1-x_2$. Hence all solutions differ by integer multiples of $M$, giving the full form
$$ x=kM + \sum_{i=1}^{n}a_it_iM_i $$