写成数论记号:同余号≡以下简记为==
x==2 mod 3
==3 mod 5
==2 mod 7
这在数论中称为同余方程组,简称同余式组。
中国剩余定理就是求解同余式组的手段之一(注意,并不是唯一方法)。它的思想是这样的:
求出
x1==1 mod 3
==0 mod 5
==0 mod 7
x2==0 mod 3
==1 mod 5
==0 mod 7
x3==0 mod 3
==0 mod 5
==1 mod 7
那么2x1+3x2+2x3即为所求解x。
如果用我引进的向量记法(近来我发现网上也有作者有类似记法),就更容易理解:
原题:x==(2,3,2) mod (3,5,7)
孙子定理:x1==(1,0,0);x2==(0,1,0);x3=(0,0,1)
x==2x1+3x2+2x3.
在求解x1时,显然x1==(0,0)mod (5,7),即x1被5,7整除。从而可设x1=5*7*k1==1 mod 3.
这里k1就是人们所说的乘率,古人求k1常用的就是大衍求一术。
这种方法实际上就是分化了维度,通过单位向量简化问题。近世代数的许多观点与方法,与这不谋而合,实际是受了中国剩余定理的启发。还有拉格朗日插值法,也与此一致。
同时我们还可以看到,x==(2,3,2) mod (3,5,7)
还可以等效于x==(2,2,2)+(0,1,0),这样无疑是对上述算法的一种改进。正如牛顿插值法相对于拉格朗晶插值的改进。
还有很多例题,如果套用中国剩余定理,实际上还不如活用巧用。那么活用巧用的规律在哪里?这便是对中国剩余定理的改进。基于我的心得和笔记,我认为,中国剩余定理大有改进余地。
基于同余式组(就是以上类别的同余方程组),柯召·孙琦<数论讲义I>中,自然地引进了模余计数法。
我,基于其求解过程,建立了一种类似于向量的记法,矩阵的记法(称之为模积计数法。)并给出转化的快捷运算方案。
[求解过程就是二者的转换过程。用现代矩阵论的成果,并考虑到其中的对称性,可以简化中国剩余定理,进行非常快捷的计算.]
更多内容请参见我的文章:中国剩余定理大有改进余地-连分数-Lucas序列-欧几里德算法(辗转相除)-类矩阵符号记法
http://hi.baidu.com/wsktuuytyh/blog/item/bfb0c64c5580fafcd72afcb9.html
后面那道题:
x==5 mod 9
==1 mod 7
==2 mod 5
我提示一下:设x=5*7*k1+5*9*k2+7*9*k3,由条件,求出k1,k2,k3,然后代入即可求得。
dfjsdfdvjkxchvjsdklkhdshfsdlkhf