跳去內容

中國剩餘定理

出自維基百科,自由嘅百科全書
(由孫子定理跳轉過嚟)

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

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

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

孫子定理

[編輯]

同埋

如果,咁就會有一個符合

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

同埋

如果,咁就會有一個符合

求解

[編輯]

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

得知,即係有一個符合

得知

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

可以推出

所以因為,簡化程序叫,即係

根據定義,有一個會符合

所以得出嘅解就係

例子

[編輯]

得知,有一個整數符合

,得出

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


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

睇埋

[編輯]