孫子定理
程式可以計算孫子定理(又稱中國餘數定理Chinese remainder theorem)的問題,程式亦容許計算N組聯立同餘式(Simultaneous linear congruences),求出最小的正整數解。
程式編寫日期: 2006年9月24日
這個程式需要使用兩個程式位置。注意: 請先輸入程式的第一部份後,再輸入程式的第二部份。
程式第一部份(儲存於P1)長度: 6步 (注意: A是按 FMLA ab/c, B是按 FMLA 。''')
KAC | 1 | Kin 4 | A 1 | B 1 |
Kin - 1 | MODE . |
程式第二部份(儲存於P2)長度: 23步
注意: 輸入程式前請先按 MODE 1 DEC MODE 0 以確保程式能正確輸入
Kout 2 | Kin + 1 | Kout 1 | ÷ | Kout 4 |
- | MODE 1 | MODE 0 | = | x2 |
x > 0 | Kout 3 | Kin + 1 | Kout 1 | ENT 1 |
Kin 3 | Kin - 1 | Kout 4 | Kin × 2 | Kout 2 |
Kin - 1 | D 2 | x > 0 | MODE . |
例題1: 一正整數被3除餘2;被5除餘3;被7除餘2,求這個的最少值。
按 P1 2 RUN 3 RUN
再按 SHIFT P2 3 RUN 5 RUN 2 RUN 7 RUN (顯示答案為23)
計算完結後按 AC 終止程式
實際上通解 = 23 + (3×5×7)n = 23 + 105n
例題2: 計算以下聯立同餘式:
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
x ≡ 3 (mod 11)
按 P1 1 RUN 2 RUN
再按 SHIFT P2 2 RUN 3 RUN 3 RUN 5 RUN 2 RUN 7 RUN 3 RUN 11 RUN (顯示答案為443)
計算完結後按 AC 終止程式
實質上通解 = 443 + (2×3×5×7×11)n = 443 + 2310n
注意: 輸入的任意兩個除數必須為互質,否則計算的解可能不是最小的解。