孫子定理

更新日期: 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

例題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