
使用中国剩余定理(又名孙子定理,出自 孙子算经 ),不过也容易发现其中余数的规律,然后解决问题更容易。
x=-1+(x+1)
x+1≡(0;0;0;0;0;1) mod (2;3;4;5;6;7)
故x+1≡lcm[2;3;4;5;6]*(1/lcm[2;3;4;5;6]mod7) mod lcm[2;3;4;5;6;7]
=120* (1/120 mod 7,见注释) mod 420
≡120 *1 mod 420
故x≡119 mod 420
注释:
以上y≡1/120 mod 7 <=>120y ≡1 <=>y≡1 mod 7
再如z≡(1;2;3;0) mod (3;5;7;11)
易见2z+1≡(0;0;0;1) mod (3;5;7;11)
或z≡(-1/2;-1/2;-1/2;0) mod (3;5;7;11)
或z≡-1/2+ (0;0;0;1/2) mod (3;5;7;11)
于是z≡-1/2+1/2*(3*5*7)* ((1/3*5*7)mod11) mod (3*5*7*11)
≡-1/2+1/2*105* (2 mod 11) mod (3*5*7*11)
≡1/2*(-1+105*13)=682 mod 1155
或者≡(3*5*7*11-1)/2+105*(1/2)*2=682
