中國剩餘定理

引言

提出問題

孫子算經問曰：今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問：物幾何？
即：

$x\equiv 2{\pmod {3}},\ x\equiv 3{\pmod {5}},\ x\equiv 2{\pmod {7}},\ x=?$

古人的解答

孫子解答

孫子算經答曰：二十三。
術曰：三三數之，賸二，置一百四十；五五數之，賸三，置六十三；七七數之，賸二，置三十。並之，得二百三十三，以二百一十減之，即得。
凡三三數之，賸一，則置七十；五五數之，賸一，則置二十一；七七數之，賸一，則置十五。一百六以上，以一百五減之，即得。

秦九韶解答

（大衍求一术）

程大位解答

《算法統宗》曰：

三人同行七十稀

五樹梅花廿一枝

七子團圓正月半

除百零五便得知

即：

$x=2\times 70+3\times 21+2\times 15=233\equiv 23{\pmod {105}}$

中國剩餘定理的命題

设：$m_{1},m_{2},\cdots ,m_{n}$为两两互素的一组整数，则关于$\left.x\right.$的方程组：

$\left\{{\begin{matrix}x\equiv a_{1}{\pmod {m_{1}}}\\x\equiv a_{2}{\pmod {m_{2}}}\\\vdots \qquad \qquad \qquad \\x\equiv a_{n}{\pmod {m_{n}}}\end{matrix}}\right.$

有唯一解。