[算法]物不知数 – 中国剩余定理

　　《孙子算经》有云：

今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问物几何？
答曰：二十三。

　　设”此物”为x，则x满足同余方程组：
$\left\{\begin{array}{c}x\equiv 2 (\mod 3)\\x\equiv 3 (\mod 5) \\x\equiv 2 (\mod 7)\end{array}\right.$
　　若存在x满足上述方程组，则 $x + k*3*5*7$ 也满足该方程其中k任意整数，方程的最小正整数解满足 $x\mod{3*5*7}$ ，即对3,5,7的最小公倍数求余。
　　在介绍求x的具体方法之前，先介绍两个简单的定理(证明从略)：

被除数增加(或减少)除数的倍数，除数不变，则余数电不变；
被除数扩大(或缩小)指定的倍数，除数不变，则余数扩大(或缩小)同样的倍数(余数总小于除数)。

　　接下来，我们这样构造满足条件的x：x由三项相加得出，其中第一项是5和7的倍数且被3除余2，第二项是3和7的倍数且被5除余3，第三项是3和5的倍数且被7除余2。即 $x=5*7*p+3*7*q+3*5*t.(p,q,t\in \mathbf{Z})$ 。又由于：
$5*7\equiv 2(\mod 3).$ 所以 $5*7*2\equiv 1 (\mod 3)$ ，于是 $5*7*2*2\equiv 2 (\mod 3)$ ;
$3*7\equiv 1(\mod 5).$ 所以 $3*7*3\equiv 3 (\mod 5)$ ;
$3*5\equiv 1(\mod 7).$ 所以 $3*5*2\equiv 2 (\mod 7)$ .
最后， $x=5*7*2*2+3*7*3+3*5*2=233\equiv 23 (\mod 105).$
反复观察上述构造过程，我们就不难从中找出规律，而这个规律就是下面要介绍的中国剩余定理，又称孙子定理。它说的是，设 $n\ge2, a_1,a_2,\ldots,a_n$ 为互质整数。 $M=a_1\cdot a_2 \cdots a_n$ 为最小公倍数。又有关于W的同余方程组如下：
$\left\{\begin{array}{l}W\equiv r_1 (\mod a_1)\\W\equiv r_2 (\mod a_2)\\\vdots\\W\equiv r_n (\mod a_n)\end{array}\right.$
该方程组有且仅有解
$W=M_1\cdot\alpha_1\cdot r_1 + M_2\cdot\alpha_2\cdot r_2+\cdots+M_n\cdot\alpha_n\cdot r_n$
其中， $M_i=a_1\cdot a_2\cdots a_{i-1}\cdot a_{i+1}\cdots a_n$
$\alpha_i$ 为调整因子，使得 $M_i\cdot\alpha_i\equiv 1(\mod a_i)$ 。