孫子定理

更新日期: 2011年8月21日

程式可以計算孫子定理(中國餘數定理Chinese Remainder Theorem)的問題,程式會計算最小正值解及其通解。要注意這個定理的限制條件,就是任何兩個除數必須為互質關係,否則計算不成立。若果希望計算更一般情況下的聯立同餘式問題,請使用聯立同餘式(I)聯立同餘式(II)程式進行計算。

程式 (58 bytes,使用記憶A, B, C及M)

程式需要在 BASE 模式下執行,因此在選擇新程式位置後,按 3 選用BASE模式。

Dec: ?→M: ?→C: While 1: ?→A: ?→B:

AM-: Lbl 1: M - M÷B×B => CM+ => Goto 1:

AM+: BC→C: Ans→B: M→A: WhileEnd

註: 如果是使用fx-50FH,上述程式中的乘號 ×可以省略不輸入,程式長度可節省1 byte。

 

例題1: 一正整數被3除餘2;被5除餘3;被7除餘2,求這個的最少值。

按 Prog 1 再按  2 EXE 3 EXE 3 EXE 5 EXE 2 EXE 7 EXE (顯示答案為23) EXE (顯示105)

所以通解 = 23 + 105n

計算完結後按 AC 終止程式

 

例題2: 計算以下聯立同餘式:

x ≡ 1 (mod 2)

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

x ≡ 3 (mod 11)

按 Prog 1 再按 EXE 2 EXE 2 EXE 3 EXE 3 EXE 5 EXE 2 EXE 7 EXE

3 EXE 11 EXE (顯示答案為443) EXE (顯示2310)

所以通解 = 443 + 2310n

計算完結後按 AC 終止程式

 

注意: 輸入的任意兩個除數必須為互質,否則計算的解可能不是最小的解。

註: 若果計算大除數問題,時間可能會很長,這是定理本身的缺點,建議使用聯立同餘式(II)程式。

 

返回 CASIO fx-50FH、fx-3650P II、fx-50FH II及fx-50F PLUS 程式集

 

相關程式:

聯立同餘式(I)

聯立同餘式(II)

有關聯立同餘式的參考資料:

孫子定理

simultaneous linear congruences

Free Web Hosting