孫子定理

出自維基百科,自由嘅百科全書
跳去: 定向搵嘢

孫子定理(Chinese Remainder Theorem),又叫中國餘數定理,係數論上面一條基礎嘅定理。

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

其實佢哋只係解緊以下呢一個同餘線性系統:

孫子定理[編輯]

同埋

如果,咁就會有一個符合

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

同埋

如果,咁就會有一個符合

求解[編輯]

求解亦係證明孫子定理嘅方法之一。設同埋。如果,求嘅解。

得知,即係有一個符合

得知

計算上面

因為,根據比舒公式,就會有兩個符合

可以推出

所以

因為,簡化程序叫,即係

根據定義,有一個會符合

所以得出嘅解就係

例子[編輯]

得知,有一個整數符合

,得出

計算

利用輾轉相除法
將利用上面整條比舒公式出嚟,
得知,
所以有一個整數符合,而最新嘅解就係

計算

利用輾轉相除法
將利用上面整條比舒公式出嚟,
得知,
所以有一個整數符合,而解就係

睇埋[編輯]