什么叫中国剩余定理
题目
什么叫中国剩余定理
答案
如果正整数m1、m2、……、mk两两互质,那么同余方程组
x≡a,(mod mi),i=1,2,……k 有无穷多解.且这些解关于模 M=m1,m2,……,mk同余,可表成
x≡a1,M'1M1+a2M'2M2+……+akM'KMK(mod M).
其中Mk=M/m,而M'k是满足M'kMk=1(mod mk)的正整数.这一算法后来传入西方,被称为中国剩余定理.
注:互质,也称互素.即两个数的最大公约数(最大公共因数,great common divisor)为1,记号:gcd(a,b)=1.
名题:
三三数之剩二,置一百四十,五五数之剩三,置六十三,七七数之剩二,置三十,并之,得二百三十三,以二百一十减之,即得.凡三三数之剩一,则置七十,五五数之剩一,则置二十一,七七数之剩一,则置十五,即得.
即:
1、将军点兵,三三数余2,五五数余3,七七数余2.问兵几何?
2、今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?——《孙子算经》
由于孙子算经成书较早,并且较早地介绍了这样的问题,故中国剩余定理的众多异名中,一个著名的另名是:孙子定理.
写成数论记号:同余号≡以下简记为==
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),这样无疑是对上述算法的一种改进.正如牛顿插值法相对于拉格朗晶插值的改进.
以上内容,来自wsktuuytyh (用户名来源于姓名的五笔编码:wsk 何 tuu 冬 ytyh 州)的百度答题与博文.欢迎引用.欢迎交流.
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
- 化学在各个实验中,玻璃棒的作用分别是什么?求全的哈~
- 《去打开大自然绿色的课本》的诗歌结尾和开头一样,这样写有什么好处?
- 石油 水力发电 风能 核能哪个与太阳能有关
- 为什么老师不在时我们在教室里说闲话 教室很吵 会突然有一瞬间特别安静
- 25乘3.2乘12.5 脱式
- 1图中此时是春秋分节气,太阳直射点的地理坐标是______
- 人站在岸边看水中物体,看到的是偏什么的什么像.潜水员在水中看岸上物体,看到的是偏什么的什么像
- 春这篇文章的第六自然段的赏析,从特点,顺序,修辞手法那些.的赏析.100字到150字.
- 六氟合铝的稳定常数
- 甲、乙两地相距600km,两车同时从两地相向出发,3小时后,两车已行路程与剩下路程比是2比3.
热门考点
- 伦敦奥运会金牌有多少克重,是纯金的吗?
- 期中考试语文82,英语82,都是满分100分的,
- 八年级的物理电路图我怎么都不懂
- 关于切割磁感线有效长度的问题,
- 帮忙看两个物理题.
- 一个高为 8dm的水桶,装满半桶水,倒出12升,剩下的重量是水桶容积的5分之2,底面积是多少平方分米
- 已知甲乙两个商店练习本的标价都是每本1元.但甲商店的优惠条件是:购买10本以上,从第11本开始按标价的7折
- 求ly=log(4)(x平方+8)定义域 值域.求log(2)(x-2)定义域、值域.
- 对建筑物进行沉降观测时,观测点宜设在什么位置?
- 100以内的数中,是3个不同的质数的积的最大数是?