中国剩余定论

引言

提出问题

孙子算经问曰：今有物，不知其数。三三数之，剩二；五五数之，剩三；七七数之，剩二。问：物几何？
即：

$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.$

有唯一解。