Sun Tsu's Extraordinary Work: Chinese Remainder Theorem

Sun Tsu's Extraordinary Work: Chinese Remainder Theorem

A main discipline of linear algebra is to study the decomposition of "spaces". That is to say, to split a space to its non-splittable subspaces. Interestingly, in the discrete case, we have an analogue for this, which involves the decomposition of congruence classes.

This problem was first solved by the great Chinese mathematician Sun Tsu, and later generalized by Qin Jiushao.

The original solution by Sun Tsu can be quoted as

There is an unknown number of something.
If we count in three-s, there would be two remaining.
If we count in five-s, there would be three remaining.
If we count in seven-s, there would be two remaining.
What is the number of the thing we have?

The solution is

$$x=(2\times70+3\times21+2\times15)+105k \ where\space k\in\mathbb{Z}$$

But why those magic numbers? The key to solving the problem apparently lies in the numbers 70, 21 and 15.
By modular arithmetic, we can easily find out that
$$
70\equiv
\begin{cases}
1 \pmod{3} \ 0 \pmod{5} \ 0 \pmod{7}
\end{cases}
,21\equiv
\begin{cases}
0 \pmod{3} \ 1 \pmod{5} \ 0 \pmod{7}
\end{cases}
,15\equiv
\begin{cases}
0 \pmod{3} \ 0 \pmod{5} \ 1 \pmod{7}
\end{cases}
$$
What have appeared in your mind? Remember the Cartesian coordinate system and the vectors. They look just like unit vectors!
Thus just like the vector bases in geometry, such "unit vectors" can form every number in the $\pmod{357}$ system.

Now we have found the key to the problem. But how can we obtain the key, in general?
Notice that $5\times7,3\times5,3\times7$ are all relatively prime, thus we have by Bezout's theorem
$$\text{There exists } u_1,u_2\text{ and } u_3\text{ such that } \ u_1\times5\times7+u_2\times3\times5+u_3\times3\times7=1$$
Solving $u_1,u_2,u_3$ reveals that $u_1\times 5 \times 7$ is 70, and so on.

Similarly we can prove the following theorem:

First consider the system of congruences
$$
\begin{cases}
x \equiv b_1 & \pmod{n_1} \
\quad \cdots \
x \equiv b_k & \pmod{n_k}
\end{cases}
$$

We can first notice that, if $n_1\cdots n_k$ are all congruent pairwise, we will have by Bezout's Theorem,

$$u_1M_1+ \cdots +u_kM_k=gcd(M_1, \cdots, M_k)=1 \ where\space M_i=\frac{n_1\cdots n_k}{n_i}$$

This actually has already solved the system above. If we take $e_i=u_iM_i$, then all possible solutions can be expressed as
$$x\equiv b_1e_1+\cdots +b_ke_k\pmod{n_1\cdots n_k}$$

But this solution lacks practical usability. This is because that, although seeming simple, the calculation of Bezout's equation is calculation intensive for human beings. So an alternative way to calculate the $u_i$ has to be developed.

Again by examining the Bezout's equation, we can notice that if we use modular arithmetic, the formula should be simpler, as it is established by a modular relationship. Trying to apply $\pmod{n_i}$ on the equation reveals that $u_iM_i\equiv 1 \pmod{n_i}$, so similarly we have $$u_1M_1+ \cdots +u_kM_k\equiv 1 \pmod{n_1\cdots n_k} \ where\space M_i=\frac{n_1\cdots n_k}{n_i}$$

Now let's view the Sun Tsu's theorem in another aspect. From above we have already known that the solution exists and is unique in the meaning of $\pmod{n_1\cdots n_k}$. Obviously $x$ stands for any number in the congruent ring $\mathbb{Z}/m\mathbb{Z}$. Thus the solution suggests a decomposition of $\mathbb{Z}/m\mathbb{Z}$ into "subspaces", which can be denoted as
$$ \mathbb{Z}/m\mathbb{Z}=\mathbb{Z}\bar{e_1}\oplus\cdots \oplus\mathbb{Z}\bar{e_k}$$

the $\oplus$ stands for "direct sum", which says that the decomposition is unique (because the Bezout's formula is unique mod n).
The same "direct sum" also applies to matrices, as matrix is an expression form of a space.