聯立同餘式(I)

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

程式編寫日期: 2006年8月15日

程式需要在 BASE 模式下執行,因此在輸入程式前請先按 Mode Mode 3 進入BASE模式。

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

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

B(0>MM+: Lbl 0: ?→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 => A→C => Goto 2:

BD÷A→B: Ans→D: M→C: Goto 0

程式精簡版 (93 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終止程式。

 

返回 fx-3650P及SC-185 程式集

孫子定理 (中國餘數定理Chinese Remainder Theorem) (59 bytes)

聯立同餘式(II)

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

孫子定理

simultaneous linear congruences

Free Web Hosting