中國剩餘定理

(由孫子定理跳轉過嚟)

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

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

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

孫子定理

編輯

 同埋 

如果 ,咁就會有一個 符合 

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

 同埋 

如果 ,咁就會有一個 符合 

求解

編輯

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

 得知 ,即係有一個 符合 

  得知 

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

 可以推出   

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

根據定義,有一個 會符合 

所以得出嘅解就係 

例子

編輯

 

 得知,有一個整數 符合 

  ,得出 

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

  


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

睇埋

編輯