中國剩餘定理

引言

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

x \equiv 2 (\mod 3), x \equiv 3 (\mod 5), x \equiv 2 (\mod 7), x = ?

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

（大衍求一术）

《算法統宗》曰：

三人同行七十稀

五樹梅花廿一枝

七子團圓正月半

除百零五便得知

即：

x = 2 \times 70 + 3 \times 21 + 2 \times 15 = 233 \equiv 23 (\mod 105)

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

{\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ ⋮ \\ x \equiv a_{n} (\mod m_{n}) \end{matrix}

有唯一解。