中國剩餘定理

中國剩餘定理（英文：Chinese Remainder Theorem），又叫中國餘數定理、孫子定理，係數論上面一條基礎嘅定理。

喺古時嘅中國，韓信點兵就係運用孫子定理。喺南北朝時期，已經有數學著作《孫子算經》問：「有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？」而喺宋朝，數學家秦九韶係《數書九章》入面答：「三人同行七十希，五樹梅花廿一支，七子團圓正半月，除百零五便得知。」

其實佢哋只係解緊以下呢一個同餘線性系統：$${\begin{cases}x\equiv 2\mod 3\\x\equiv 3\mod 5\\x\equiv 2\mod 7\end{cases}}$$

孫子定理

設$a,b\in \mathbb {Z}$同埋$m,n\in \mathbb {N}$。

如果$\gcd(m,n)=1$，咁就會有一個$x\in \mathbb {Z}$符合${\begin{cases}x\equiv a\mod m\\x\equiv b\mod n\\\end{cases}}$。

呢個版本可以推斷到有限咁多條式嘅版本：

設$a_{1},a_{2},\cdots ,a_{n}\in \mathbb {Z}$同埋$b_{1},b_{2},\cdots ,b_{n}\in \mathbb {Z}$。

如果$\gcd(b_{1},b_{2},\cdots ,b_{n})=1$，咁就會有一個$x\in \mathbb {Z}$符合${\begin{cases}x&\equiv a_{1}\mod b_{1}\\x&\equiv a_{2}\mod b_{2}\\\vdots &\equiv \vdots \mod \vdots \\x&\equiv a_{n}\mod b_{n}\\\end{cases}}$。

求解

求解亦係證明孫子定理嘅方法之一。設$a,b\in \mathbb {Z}$同埋$m,n\in \mathbb {N}$。如果$\gcd(m,n)=1$，求${\begin{cases}x\equiv a\mod m-(1)\\x\equiv b\mod n-(2)\\\end{cases}}$嘅解。

由$(1)$得知$x-a|m$，即係有一個$p\in \mathbb {Z}$符合$mp=(x-a)$。

代$x=mp-a$去$(2)$得知$mp-a\equiv b\mod n$。

計算上面$${\begin{aligned}mp-a&\equiv b&\mod n\\mp&\equiv a+b&\mod n\\\end{aligned}}$$因為$\gcd(m,n)=1$，根據比舒公式，就會有兩個$c,d\in \mathbb {Z}$符合$mc+nd=1$。

由$mc+nd=1$可以推出$nd=1-mc$，$n|1-mc$，$mc\equiv 1\mod n$。

所以$${\begin{aligned}mp&\equiv a+b&\mod n\\(cm)p&\equiv c(a+b)&\mod n\\p&\equiv c(a+b)&\mod n\end{aligned}}$$因為$c(a+b)\in \mathbb {Z}$，簡化程序叫$z=c(a+b)$，即係$p\equiv z\mod n$。

根據定義，有一個$f\in \mathbb {Z}$會符合$p-z=fn$。

所以得出嘅解就係$x=m(fn+z)-a$

例子

解${\begin{cases}x\equiv 2\mod 3\\x\equiv 3\mod 11\\x\equiv 2\mod 7\end{cases}}$。

由$x\equiv 2\mod 3$得知，有一個整數$m\in \mathbb {Z}$符合$3m=x-2$。

代$x=3m+2$入$x\equiv 3\mod 11$，得出$3m+2\equiv 3\mod 11$。

計算$${\begin{aligned}3m+2&\equiv 3\mod 11\\3m&\equiv 1\mod 11\\\end{aligned}}$$利用輾轉相除法，$${\begin{aligned}11&=3\times 3+2\\3&=2\times 1+1\\\end{aligned}}$$將利用上面整條比舒公式出嚟，$${\begin{aligned}1&=3-2\times 1\\&=3-(11-3\times 3)\\&=3-11+3\times 3\\&=3\times 4-11\end{aligned}}$$得知，$${\begin{aligned}3m&\equiv 1\mod 11\\(4\times 3)m&\equiv 4\times 1\mod 11\\m&\equiv 4\mod 11\end{aligned}}$$所以有一個整數$n\in \mathbb {Z}$符合$m=11n+4$，而最新嘅解就係$x=3m+2=3(11n+4)+2$。

代$x=3m+2=3(11n+4)+2$去$x\equiv 2\mod 7$。

計算$${\begin{aligned}3(11n+4)+2&\equiv 2\mod 7\\33n+14&\equiv 2\mod 7\\33n&\equiv 2\mod 7\end{aligned}}$$利用輾轉相除法，$${\begin{aligned}33&=7\times 4+5\\7&=5\times 1+2\\5&=2\times 2+1\end{aligned}}$$將利用上面整條比舒公式出嚟，$${\begin{aligned}1&=5-2\times 2\\&=5-(7-5\times 1)\times 2\\&=5\times 3-7\times 2\\&=(33-7\times 4)\times 3-7\times 2\\&=33\times 3-7\times 12-7\times 2\\&=33\times 3-7\times 14\end{aligned}}$$得知，$${\begin{aligned}33n&\equiv 2\mod 7\\(3\times 33)n&\equiv 3\times 2\mod 7\\n&\equiv 6\mod 7\end{aligned}}$$所以有一個整數$l\in \mathbb {Z}$符合$n=7l+6$，而解就係$x=3m+2=3[11(7l+6)+4]+2$。

睇埋

• 餘數定理
• 輾轉相除法
• 同餘