聯立同餘式(I)

更新日期: 2014年8月21日

程式可以求整數論中聯立同餘式(simultaneous linear congruences) 的解,程式會計算最小正值解及通解。 程式沒有使用中國餘數定律的限制,即是沒有任何兩個除數有互質關係的限制,而且可以直接輸同餘數數值代替餘數,甚至可以計算各種負數情況。若果只計算中國餘數定理的簡單問題,可以使用較簡單孫子定理程式(58 bytes)。不過程式與使用中國餘定理程式相同,在計算較大除數時,例如: 計算 聯立同餘式X≣123 (mod 9877) 及 X≣923 (mod 8979)時, 速度可能會非常慢,基本上可以說無法求得答案,若果希望同時克服這方面的問題,請使用聯立同餘式(II)程式

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

程式 (128 bytes,使用記憶為A、B、C、D、X及M)

Dec: ?→M: ?→B: 0>B => - B→B: M÷B×BM-:

B(0>MM+: While 1: ?→C: ?→D: CM-: 0>D => - D→D:

Lbl 1: M - M÷D×D => BM+ => Goto 1: CM+: B→C:

D→X: Lbl 2: X→A: C - C÷X×X→X: Ans => A→C:

Ans => Goto 2: BD÷A→B: Ans→D: M→C: WhileEnd

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

 

例題1: 計算以下聯立同餘式(除數間亦可以是不是互質):

x ≡ 4 (mod 5)

x ≡ 1 (mod 3)

x ≡ 9 (mod 10)

按 Prog 1  4 EXE 5 EXE 1 EXE 3 EXE 9 EXE 10 EXE (顯示19) EXE (顯示30)

所以最小的正值為19,通解 = 19 + 30n

計算完結按MODE 1終止程式及返回comp MODE

 

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

x ≡ 4 (mod 5)

x ≡ 1 (mod 3)

x ≡ 9 (mod 10)

x ≡ 2 (mod 7)

x ≡ 7 (mod 12)

按 Prog 1 再按 4 EXE 5 EXE 1 EXE 3 EXE 9 EXE 10 EXE 2 EXE 7 EXE

7 EXE 12 EXE (顯示79) EXE (顯示420)

所以最小的正值為79,通解 = 79 + 420n

計算完結按MODE 1終止程式及返回comp MODE

 

註1: 若果要輸入負數,請用減號代替負號。

註2: 若果方程無解,計算機會不停運算(空白),請按AC終止程式。

 

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