引入 我國古代數學著作《孫子算經》中有一道題目，它的描述是這樣的 今有物不知其數，三三數之餘二；五五數之餘三；七七數之餘二。問物幾何？ 這道題用現代數學理論來看，無非就是解一個方程 \begin{cases}x\equiv 2\left( mod\ 3\right) \\x\equiv 3\left ...
引入
我國古代數學著作《孫子算經》中有一道題目，它的描述是這樣的
今有物不知其數，三三數之餘二；五五數之餘三；七七數之餘二。問物幾何？
這道題用現代數學理論來看，無非就是解一個方程
\begin{cases}x\equiv 2\left( mod\ 3\right) \\
x\equiv 3\left( mod\ 5\right) \\
x\equiv 2\left( mod\ 7\right) \end{cases}
那麼這個方程怎麼解呢？
這需要用到我們祖先的偉大創造——中國剩餘定理
中國剩餘定理
在很久以前，數學領域還沒有像擴展歐幾裡得這種東西。對於這個問題，我們祖先採用了構造的方法
構造過程如下
首先考慮三個特殊方程
\begin{cases}x\equiv 1\left( mod\ 3\right) \\
x\equiv 0\left( mod\ 5\right) \\
x\equiv 0\left( mod\ 7\right) \end{cases}
\begin{cases}x\equiv 0\left( mod\ 3\right) \\
x\equiv 1\left( mod\ 5\right) \\
x\equiv 0\left( mod\ 7\right) \end{cases}
\begin{cases}x\equiv 0\left( mod\ 3\right) \\
x\equiv 0\left( mod\ 5\right) \\
x\equiv 1\left( mod\ 7\right) \end{cases}
他們的特殊解
那第一個方程來說，它實際上等同於解一個同餘式
$$35y\equiv 1\left( mod\ 3\right) $$
因為$x$一定是$5*7=35$的倍數
化簡一下當面的式子
$$2y\equiv 1\left( mod\ 3\right) $$
我們不難得出解$y=2$，此時$x=70$
同理，對於第二第三個式子我們可以運用相同的方法求解
$$\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}=70\begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}=21\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}=15$$
那麼最終的答案為
$$\begin{pmatrix} 2 \\ 3 \\ 2 \end{pmatrix}=2\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}+3\begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}+2\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}$$
$$=2\times 70+3\times 21+2\times 15\equiv 23\left( mod\ 105\right)$$
我們這樣就可以求出解了。
但是這僅僅是三個式子的情況，如果推廣到$r$個呢?
其實是一樣的，都是利用構造的手段。
下麵我們來推廣一下。
設有$r$個同餘式，其中$m_i$兩兩互素，註意$m$必須兩兩互素，否則答案錯誤。其實不互素也可以搞不過要用更神奇的東西
設$N=\prod ^{r}_{i=1}m_{i}$
對於同餘方程組
$$\begin{cases}x\equiv b_{1}\left( mod\ m_{1}\right) \\ x\equiv b_{2}\left( mod\ m_{2}\right) \\ \ldots \\ x\equiv br\left( mod\ m_r\right) \end{cases}$$
在模$N$同餘的意義下有唯一解
這個方程怎麼解呢？
我們仍然像前面一樣，考慮構造
$$\begin{cases}x\equiv 0\left( mod\ m_{1}\right) \\ \ldots \\ x\equiv 0\left( mod\ m_{i-1}\right) \\ \ldots \\ x\equiv 1\left( mod\ m_{i}\right) \\ \ldots \\ x\equiv 0\left( mod\ m_{i+1}\right) \\ \ldots \\ x\equiv0\left( mod\ M_{r}\right) \end{cases}$$
像上面那樣，我們令$x=(N/m_i)*y$
那麼我們現在需要解出
$\left( N/m_{i}\right) y\equiv 1\left( mod\ m_{i}\right) $
這個東西怎麼搞呢？
聰明的你肯定已經知道啦，這不就是個逆元嘛，想怎麼搞就怎麼搞
如果你不知道怎麼搞的話可以看這裡
那麼方程的解為$x_{0}=b_{1}x_{1}+b_{2}x_{2}+\ldots +b_{r}x_{r}\left( mod\ N\right)$
怎麼樣？似不似很簡單？
例題
有了上面的知識代碼應該不難寫
放一道水題
http://poj.org/problem?id=1006
題解（很久之前做的）
