關於不同餘問題，以前我都是用數字的性質來解題
，數字大了就不好算了，不知有無其他算法?


例:x/7餘3，x/11餘2，求x值如何表示?
:-? :-? :-?
國中

回應

孫文先

2005-09-19 18:32
可參考孫子定理。
先找出使得11a除以7餘1的值，11a=22。
再找出使得7b除以11餘1的值，7b=56。
x=(22x3+56x2)(mod 77)
故x值可以是24, 101, 178,.....

一般情況
x/a1餘r1, x/a2餘r2, x/a3餘r3,...., x/an餘rn
先找出k1a2a3a4...除以a1餘1的值s1;
找出k2a1a3a4...除以a2餘1的值s2;
找出k3a1a2a4...除以a3餘1的值s3;
.....

則x=(r1s1+r2s2+r3s3+.....+rnsn)(mod a1a2a3...an)