Prove the Chinese Remainder Theorem. In number theory, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise co-prime.Let n1, ..., nk be integers greater than 1, which are often called moduli or divisors. Let us denote by N the product of the ni.
The Chinese remainder theorem asserts that if the ni are pairwise coprime, and if a1, ..., ak are integers such that 0 ≤ ai < ni for every i, then there is one and only one integer x, such that 0 ≤ x < N and the remainder of the Euclidean division of x by ni is ai for every i.
This may be restated as follows in term of congruences: If the ni are pairwise coprime, and if a1, ..., ak are any integers, then the system
\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}
has a solution, and any two solutions, say x1 and x2, are congruent modulo N, that is, x1 ≡ x2 (mod N).
[Wikipedia]
I have already tried thinking about the case of it's $mod$ $2$, but can't really think about anything else. Can anyone help please?
 A: First solve the $n=2$ case. That is
\begin{align*}
x&\equiv a(\text{mod }p)\\
x&\equiv b(\text{mod }q)
\end{align*}
Now, define $p_1$ and $q_1$ such that $p_1p\equiv 1(\text{mod }q)$ and $q_1q\equiv 1(\text{mod }p)$. The existence of these are guaranteed by the fact that $p$ and $q$ are coprime$^*$. Now let
$$y \equiv a q q_1 + b p p_1 (\text{mod }pq)$$
Then $y$ satisfies both the equations. This is because, when we consider modulo $p$, we get $y\equiv aqq_1\equiv a(\text{mod }p)$. Similarly, $y\equiv b(\text{mod }q)$. So, $y$ is a solution for $x$.
To show the uniqueness of this solution, note that if $z\equiv a(\text{mod }p)$ and $z\equiv b(\text{mod }q)$, we have $(z-y)$ is a multiple of $p$ and $q$ respectively. So, $(z-y)$ is a multiple of $pq$ which means $z\equiv y(\text{mod }pq)$
Now, for the general case of
\begin{align*}
x&\equiv a_1(\text{mod }m_1)\\
&\cdots\\
&\cdots\\
&\cdots\\
x&\equiv a_n (\text{mod }m_n)
\end{align*}
it is very easy to extend our previous idea using induction.
Using our previous idea, we can define $M=m_1m_2\cdots m_n$, $b_i=\frac M{m_i}$ and $b_i^{\prime}=b_i^{-1}$ for all $i$ and note that
$$x\equiv \sum_{i=1}^n a_i b_i b_i^{\prime} (\text{mod }m)$$

$*$ Since $p$ and $q$ are coprime, there are integers $a$ and $b$ such that $ap+bq=1$ (by Euclid's Division Algorithm). Now, put $a=p_1$ and $b=-k$.
