一个数被2除余1,被3除余2,被4除余3,被5除余4,被6除余5,被7整除,这个数是多少?

一个数被2除余1,被3除余2,被4除余3,被5除余4,被6除余5,被7整除,这个数是多少?

使用中国剩余定理(又名孙子定理,出自 孙子算经 ),不过也容易发现其中余数的规律,然后解决问题更容易。

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

标签:除余,数是,整除,数论,趣味数学,初中数学,初等数论,初等代数