中國剩餘定理(英文:Chinese Remainder Theorem),又叫中國餘數定理、孫子定理,係數論上面一條基礎嘅定理。
喺古時嘅中國,韓信點兵就係運用孫子定理。喺南北朝時期,已經有數學著作《孫子算經》問:「有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?」而喺宋朝,數學家秦九韶係《數書九章》入面答:「三人同行七十希,五樹梅花廿一支,七子團圓正半月,除百零五便得知。」
其實佢哋只係解緊以下呢一個同餘線性系統:
![{\displaystyle {\begin{cases}x\equiv 2\mod 3\\x\equiv 3\mod 5\\x\equiv 2\mod 7\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c90722a4f42ac1898e3c9f5807147c799d07f5e8)
孫子定理[編輯]
設
同埋
。
如果
,咁就會有一個
符合
。
呢個版本可以推斷到有限咁多條式嘅版本:
設
同埋
。
如果
,咁就會有一個
符合
。
求解亦係證明孫子定理嘅方法之一。設
同埋
。如果
,求
嘅解。
由
得知
,即係有一個
符合
。
代
去
得知
。
計算上面
![{\displaystyle {\begin{aligned}mp-a&\equiv b&\mod n\\mp&\equiv a+b&\mod n\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b6476d07b053a25dfc91bfb678ecc288166e592)
因為
![{\displaystyle \gcd(m,n)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f43c4052a27ae23281e912d3e0b50357ff5f16a6)
,根據
比舒公式,就會有兩個
![{\displaystyle c,d\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/82f081a12b502bce23c8ba8baa3671de28c52635)
符合
![{\displaystyle mc+nd=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f1f1b87164a8eb5b02551e8cfbf5460771f38e6)
。
由
可以推出
,
,
。
所以
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa21109e4be85ce27323159f9515278711d36d3d)
因為
![{\displaystyle c(a+b)\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c2ceb224691e9b6e09b5e3ba5bf3b83bd2ae21d)
,簡化程序叫
![{\displaystyle z=c(a+b)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/435972b7a41fa0b1bec1ba91912e65c65133f58c)
,即係
![{\displaystyle p\equiv z\mod n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28c647eebfa3327635b23c5422a08f7b78767ef2)
。
根據定義,有一個
會符合
。
所以得出嘅解就係
解
。
由
得知,有一個整數
符合
。
代
入
,得出
。
計算
![{\displaystyle {\begin{aligned}3m+2&\equiv 3\mod 11\\3m&\equiv 1\mod 11\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bdc181204c89aa1e4c04f5ae289e9f414b63c922)
利用
輾轉相除法,
![{\displaystyle {\begin{aligned}11&=3\times 3+2\\3&=2\times 1+1\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f88bbb7a9a1817235ea975fc617e65754f426ef)
將利用上面整條比舒公式出嚟,
![{\displaystyle {\begin{aligned}1&=3-2\times 1\\&=3-(11-3\times 3)\\&=3-11+3\times 3\\&=3\times 4-11\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc3cfef7200d08239d2ebf7c38898045fd91945f)
得知,
![{\displaystyle {\begin{aligned}3m&\equiv 1\mod 11\\(4\times 3)m&\equiv 4\times 1\mod 11\\m&\equiv 4\mod 11\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0f5119d6ababffbcb298f51bb8d726d53f22a50)
所以有一個整數
![{\displaystyle n\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c1cf6a513f2062531d95dbb198944936f312982)
符合
![{\displaystyle m=11n+4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23b107b670c323b20add37e6fdeb8e6af4bd9132)
,而最新嘅解就係
![{\displaystyle x=3m+2=3(11n+4)+2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/961be929913a2f2c19ee2642da46fbd02d2dcf41)
。
代
去
。
計算
![{\displaystyle {\begin{aligned}3(11n+4)+2&\equiv 2\mod 7\\33n+14&\equiv 2\mod 7\\33n&\equiv 2\mod 7\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b38c150e3fc195077bfba978c1621d3984bbf1b)
利用
輾轉相除法,
![{\displaystyle {\begin{aligned}33&=7\times 4+5\\7&=5\times 1+2\\5&=2\times 2+1\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/025d46f4f9b98547833b373b4162e11c82cfe907)
將利用上面整條比舒公式出嚟,
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e80e2b623cc6ba5c3a3990fe0de42f1603b1d3d5)
得知,
![{\displaystyle {\begin{aligned}33n&\equiv 2\mod 7\\(3\times 33)n&\equiv 3\times 2\mod 7\\n&\equiv 6\mod 7\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/286c988b3154e3ecad4e960cfe41d7065f48abac)
所以有一個整數
![{\displaystyle l\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb0c3677d7d07beedd44861759004f5827ab99cb)
符合
![{\displaystyle n=7l+6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edd8f9963d705480ee03a8c34c2b44697ba0fcaa)
,而解就係
![{\displaystyle x=3m+2=3[11(7l+6)+4]+2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7df26f30ac2ccdeef7aa88cf3b6b1132095f4957)
。
|
---|
數論分支 | |
---|
數字概念 | |
---|
基本概念 | |
---|
基本定理 | |
---|
進階數論概念 | |
---|
進階數論理論 | |
---|
|