聯立同餘式(I)

更新日期: 2011年1月31日

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

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

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

Dec: ?→M: ?→B: 0>B => - B→B: M÷BBM-:

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

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

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

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

例題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-50F PLUS 程式集