In the most common proof of the Chinese remainder Theorem, there is this summation: $x=\sum m_1b_1a_1+m_2b_2a_2$ where $a_i$ is the inverse of $b_i$. I understand that when $i\neq j$, that $m_i\mod{j}$ is congruent to $0$. But even so, how does this summation give us the solution to a system of equations?
Thanks!
One statement of the CRT is that the function
$$f: \mathbb Z_m \to \mathbb Z_{m_1} \oplus \mathbb Z_{m_2} \oplus \cdots \oplus \mathbb Z_{m_N}$$
defined by $f(\overline x) = (\overline x, \overline x, \dots, \overline x)$ is a group isomorphism when the $m_i$ are pairwise prime and their product is $m$. In fact, it's more than that. It's a ring isomorphism. That is
$\text{$(1.) \quad f(\overline x + \overline y) = f(\overline x) + f(\overline y)$}$
$\text{$(2.) \quad f(\overline x \cdot \overline y) = f(\overline x) \cdot f(\overline y)$ where we define}$ $$(\overline{x_1}, \overline{x_2}, \dots, \overline{x_N}) \cdot (\overline{y_1}, \overline{y_2}, \dots, \overline{y_N}) = (\overline{x_1 \cdot y_1}, \overline{x_2 \cdot y_2}, \dots, \overline{x_N\cdot y_N})$$
$\text{$(3.)\quad$ f is one-to-one and onto.}$
Let's assume that this has been proved since you only want to know about where the sum comes from.
Since $f$ is an isomorphism, then $f$ has an inverse function and $f^{-1}$ is also an isomorphism.
Here's where the trick comes in. Let $M = \prod_{i=1}^N m_i$. For $i=1$ to $N$ define $$M_i=\dfrac{M}{m_i}$$. If you think about it, $M_i$ is just the product $m_1m_2m_3 \cdots m_N$ with the $m_i$ removed. Because of this, it should be clear that
$$i \ne j \implies M_j \equiv 0 \pmod{m_i}\tag{1.}$$
It turns out that
\begin{align} \gcd(\{M_i\}_{i=1}^N) &= \gcd \left(\left\{\dfrac{M}{m_i}\right\}_{i=1}^N \right)\\ &= \dfrac{M}{\operatorname{lcm}\left(\left\{\dfrac{M}{m_i}\right\}_{i=1}^N \right)} \\ &= \dfrac MM \\ &= 1 \end{align}
So there must exists integers $\{ \lambda_i \}_{i=1}^N$ such that $$\sum_{i=1}^N \lambda_i M_i = 1$$
For $i$ equals $1$ to $N$, define $u_i \equiv \lambda_iM_i \pmod M$. We know immediately (see equation $(1.)$) that $i \ne j \implies u_j \equiv \lambda_j M_j \equiv 0 \pmod{m_i}$. It follows that $1 \equiv \sum_{j=1}^N \lambda_j M_j \equiv \lambda_i M_i \equiv u_i \pmod{m_i}$. This means that
\begin{align} f(u_1) &= (1,0,0, \dots, 0) \\ f(u_2) &= (0,1,0, \dots, 0) \\ f(u_3) &= (0,0,1, \dots, 0) \\ &\phantom n\vdots \\ f(u_N) &= (0,0,0, \dots, 1) \\ \end{align}
Because $f$ is a bijection, that means that, for all $1 \le i \ne j \le N$, $u_i^2 \equiv u_i \pmod m$ and $ui \cdot u_j \equiv 0 \pmod m$.
Clearly $\displaystyle (\overline{x_1}, \overline{x_2}, \dots, \overline{x_N}) = \sum_{i=1}^N x_i f(u_i)=\sum_{i=1}^N f(x_i \cdot u_i)$