中国剩余定理

孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。
我国古代《孙子算经》的卷下第二十六题，“物不知数”题如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
答曰二十三。

物不知数问题用同余式组来表示就是：

定义：由若干个一次同余式构成的同余式组称为一次同余式组

如果存在$x_{0}\in Z$x0​∈Z，使得 $a_{i}x_{0}\equiv b_{i}\left ( mod \ m_{i} \right )\left ( i=1,\cdots ,n \right )$ai​x0​≡bi​(mod mi​)(i=1,⋯,n),则 $x\equiv x_{0}\left ( mod\left [ m_{1},m_{2},\cdots m_{n} \right ] \right )$x≡x0​(mod[m1​,m2​,⋯mn​])为同余式组的一个解。

中国剩余定理
设$m_{1},m_{2},\cdots ,m_{k}$m1​,m2​,⋯,mk​是k个两两互素的正整数，则对任意的整数$b_{1},b_{2},\cdots ,b_{k}$b1​,b2​,⋯,bk​,同余式组

有唯一解：$x\equiv M_{1}^{'}M_{1}b_{1}+M_{2}^{'}M_{2}b_{2}+\cdots +M_{k}^{'}M_{k}b_{k}\left ( mod \ m \right )$x≡M1′​M1​b1​+M2′​M2​b2​+⋯+Mk′​Mk​bk​(mod m)

其中：$m=m_{1}m_{2}\cdots m_{k}$m=m1​m2​⋯mk​, $m=m_{i}M_{i}$m=mi​Mi​, $M_{i}^{'}M_{i}\equiv 1(mod \ m_{i})$Mi′​Mi​≡1(mod mi​), i=1,2,…,k

为了方便看懂，列表可如下：
表中:
$M_{i}=\frac{m_{1}m_{2}\cdots m_{k}}{m_{i}}$Mi​=mi​m1​m2​⋯mk​​
$M_{i}^{'}M_{i}\equiv 1(mod \ m_{i})$Mi′​Mi​≡1(mod mi​)

现在回到“物不知数”问题，列表可以很容易求出结果：