UC知道孙子剩余定理 乘率求法
来源：百度知道 编辑：UC知道 时间：2024/05/31 16:20:02
“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”即被三除余二，被五除余三，被七除余二的最小整数。
解法过程为2×70+3×21+2×15-2×105=23
其中70、21、15 叫做乘率。21=3*7，15=3*5，而70=2*5*7，为什么得到70要乘以2？
解法过程为2×70+3×21+2×15-2×105=23
其中70、21、15 叫做乘率。21=3*7，15=3*5，而70=2*5*7，为什么得到70要乘以2？
写成数论记号：同余号≡以下简记为==
注:
N 除以m余r，记作N == r mod m.
N与L除以m余数相同，称作同余，记作N==L mod m.
x==2 mod 3
==3 mod 5
==2 mod 7
这在数论中称为同余方程组，简称同余式组。
中国剩余定理(孙子定理)就是求解同余式组的手段之一(注意，并不是唯一方法)。它的思想是这样的：
以下为方便说明,采用我引进的向量记法(近来我发现网上也有作者有类似记法),可写成：
x==(2,3,2) mod (3,5,7)
令
x1==(1,0,0);即x1==1 mod 3,x1==(0,0)mod(5,7),亦即x1被5,7整除.
x2==(0,1,0);
x3==(0,0,1)
那么可取
x==2x1+3x2+2x3
在求解x1时，由于x1被(5*7)整除,从而可设x1=5*7*k1;
又x1==1 mod 3,即5*7*k1==1 mod 3.
很显然可以取k1=2.这便是提问者问到的"为什么得到70要乘以2",其实取-1也行嘛.
对于此题，其实有更简当的解法，见我的另一处答题：
http://zhidao.baidu.com/question/106204827.html?si=1
这里的k1,当然是很容易求的;但对于复杂的情况,如
377873k≡1(mod499067)的乘率k(题见http://www.chinavalue.net/Blog/BlogThre