孫子定理

程式可以計算孫子定理(又稱中國餘數定理Chinese remainder theorem)的問題,程式亦容許計算N組聯立同餘式(Simultaneous linear congruences),求出最小的正整數解。

程式編寫日期: 2006年12月14日

程式第一部份長度: 8步

1 KAC 2. 1 3. Kin 4 4. ENT 5. Kin 1
6. ENT 7. Kin 2 8. Kin - 1 9.   10.  

程式第二部份長度: 25步

1 Kout 2 2. Kin + 1 3. Kout 1 4. ÷ 5. Kout 4
6. - 7. FIX 0 8. RND 9. NORM 10. =
11. x2 12. x > 0 13. Kout 3 14. Kin + 1 15. Kout 1
16. ENT 17. Kin 3 18. Kin- 1 19. Kout 4 20. Kin × 2
21. Kout 2 22. Kin - 1 23. ENT 24. Kin 4 25. x > 0

LRN 模式輸入第一部份程式(供 fx-3600PV及fx-3800P使用,程式長度: 8步 )

KAC 1 Kin 4 ENT 1 Kin 1
ENT 2 Kin 2 Kin - 1 MODE .  

LRN 模式輸入第二個程式(供 fx-3600PV及fx-3800P使用,程式長度: 25步 )

Kout 2 Kin + 1 Kout 1 ÷ Kout 4
- FIX 0 RND NORM =
x2 x > 0 Kout 3 Kin + 1 Kout 1
ENT 3 Kin 3 Kin- 1 Kout 4 Kin × 2
Kout 2 Kin - 1 ENT 5 Kin 4 x > 0
MODE .        

 

以下例題假設程式第一部份及第二部份分別儲存於P1及P2。

例題1: 一正整數3除餘2;被5除餘3;被7除餘2,求這個的最少值。

P1  2 RUN 3 RUN

再按 SHIFT P2  3 RUN 5 RUN 2 RUN 7 RUN (顯示答案為23) RUN (顯示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)

P1  1 RUN 2 RUN

再按 SHIFT P2  2 RUN 3 RUN 3 RUN 5 RUN 2 RUN 7 RUN

3 RUN 11 RUN (顯示答案為443) RUN (顯示2310)

所以通解 = 443 + 2310n

計算完結後按 AC 終止程式

 

注意: 輸入的任意兩個除數必須為互質,否則計算的解可能不是最小的解。

 

返回 fx-3900PV程式集

Free Web Hosting