中國剩餘定理(英文:Chinese Remainder Theorem),又叫中國餘數定理、孫子定理,係數論上面一條基礎嘅定理。
喺古時嘅中國,韓信點兵就係運用孫子定理。喺南北朝時期,已經有數學著作《孫子算經》問:「有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?」而喺宋朝,數學家秦九韶係《數書九章》入面答:「三人同行七十希,五樹梅花廿一支,七子團圓正半月,除百零五便得知。」
其實佢哋只係解緊以下呢一個同餘線性系統:
設同埋。
如果,咁就會有一個符合。
呢個版本可以推斷到有限咁多條式嘅版本:
設同埋。
如果,咁就會有一個符合。
求解亦係證明孫子定理嘅方法之一。設同埋。如果,求嘅解。
由得知,即係有一個符合。
代去得知。
計算上面因為,根據比舒公式,就會有兩個符合。
由可以推出,,。
所以因為,簡化程序叫,即係。
根據定義,有一個會符合。
所以得出嘅解就係
解。
由得知,有一個整數符合。
代入,得出。
計算利用輾轉相除法,將利用上面整條比舒公式出嚟,得知,所以有一個整數符合,而最新嘅解就係。
代去。
計算利用輾轉相除法,將利用上面整條比舒公式出嚟,得知,所以有一個整數符合,而解就係。
|
---|
數論分支 | |
---|
數字概念 | |
---|
基本概念 | |
---|
基本定理 | |
---|
進階數論概念 | |
---|
進階數論理論 | |
---|
|