中国剩余定理.pdf
《中国剩余定理.pdf》由会员分享,可在线阅读,更多相关《中国剩余定理.pdf(11页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、中国剩余定理孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期(公元5 世纪)的数学著作孙子算经卷下第二十六题,叫做“物不知数”问题,原文如下:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。孙子算经中首次提到了同余方程组问题,以及以上具体问题的解法,因此在中文数学文献中也会将中国剩余定理称为孙子定理。中文名孙子定理外文名Chinese remainder theorem(CRT)分类数学提出孙子问题一元线性同余方程组又名余数定理
2、目录.1 公式.2 文献.3 交换环上推广.?主理想整环.?一般的交换环.4 数论相关.5 例题解析公式用现代数学的语言来说明的话,中国剩余定理给出了以下的一元线性同余方程组:有解的判定条件,并用构造法给出了在有解情况下解的具体形式。中国剩余定理说明:假设整数m1,m2,.,mn两两互质,则对任意的整数:a1,a2,.,an,方程组有解,并且通解可以用如下方式构造得到:设是整数 m1,m2,.,mn的乘积,并设是除了 mi以外的 n-1 个整数的乘积。设为模的数论倒数(为模意义下的逆元)方程组的通解形式为在模的意义下,方程组只有一个解:证明 1:从假设可知,对任何,由于,所以这说明存在整数使得
3、这样的叫做模的数论倒数。考察乘积可知:所以满足:这说明就是方程组的一个解。另外,假设和都是方程组的解,那么:而两两互质,这说明整除.所以方程组的任何两个解之间必然相差的整数倍。而另一方面,是一个解,同时所有形式为:的整数也是方程组的解。所以方程组所有的解的集合就是:文献一元线性同余方程组问题最早可见于中国南北朝时期(公元5 世纪)的数学著作孙子算经卷下第二十六题,叫做“物不知数”问题,原文如下:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。孙子算经中首次提到了同余方程组问题,以及以上具体问题的解法,因此在中文数学文
4、献中也会将中国剩余定理称为孙子定理。宋朝数学家秦九韶于1247 年数书九章卷一、二大衍类对“物不知数”问题做出了完整系统的解答。明朝数学家程大位将解法编成易于上口的孙子歌诀:三人同行七十稀,五树梅花廿一支,七子团圆正半月,除百零五使得知这个歌诀给出了模数为3、5、7 时候的同余方程的秦九韶解法。意思是:将除以3 得到的余数乘以70,将除以5 得到的余数乘以21,将除以7 得到的余数乘以15,全部加起来后除以105(或者 105 的倍数),得到的余数就是答案。比如说在以上的物不知数问题里面,按歌诀求出的结果就是23。交换环上推广主理想整环设 R 是一个主理想整环,m1,m2,.,mk是其中的k
5、个元素,并且两两互质。令M m1m2.mn为这些元素的乘积,那么可以定义一个从商环R/MR 映射到环乘积R/m1R?R/mkR 的同态:并且是一个环同构。因此的逆映射也存在。而这个逆映射的构造方式就如同中国剩余定理构造一元线性同余方程组的解一样。由于mi和 Mi=M/mi互质,所以存在si和 ti使得而映射就是的逆映射。也是一个主理想整环。将以上的R 换成,就能得到中国剩余定理。因为一般的交换环设 R 是一个有单位元的交换环,I1,I2,.,Ik是为环的理想,并且当时,则有典范的环同构:数论相关数论 是纯粹数学的分支之一,主要研究整数的性质。按研究方法来看,数论大致可分为初等数论和高等数论。初
6、等数论是用初等方法研究的数论,它的研究方法本质上说,就是利用整数环的整除性质,主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、计算数论等等。初等数论主要就是研究整数环的整除理论及同余理论。此外它也包括了连分数理论和少许不定方程的问题。本质上说,初等数论的研究手段局限在整除性质上。初等数论中经典的结论包括算术基本定理、欧几里得的质数无限证明、中国剩余定理、欧拉定理(其特例是费马小定理)、高斯的二次互反律,勾股方程的商高定理、佩尔方程的连分数求解法等等。例题解析例一:一个数,除以5 余 1,除以 3 余 2。问这个数最小是多少?采用通用
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中国 剩余 定理
限制150内