您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 一个题根从小学讲到高中从带余除法到中国剩余定理
1一个题根从小学讲到高中----------由带余除法到中国剩余定理(一)什么是带余除法?顾名思义,带余除法就是两个整数相除,除不尽而带有余数.例如:7÷3=2…1.这个式子的含义是:7除以3是除不尽的,运算的结果是商2余1.这个式子带有省略号,不算太清楚,所以一般将其改写为;7=3×2+1.一般地,如果被除数是b,除以除数a后商数是q,余数是r,则有;baqr这个式子,是带余除法的基本公式,也是研究整除问题的题根.我们这个专题,就主要讲解并消化这个公式.千万别不屑一顾:无非是带余除法么?有什么高深莫测的?那么我且问你,以下几个问题你真的清楚吗?1.余数的基本性质.问题1.如果除数是5,那么余数有哪几种可能?【解析】直接举例,5,6,7,8,9除以5,余数分别为0,1,2,3,4;以下10,11,12,13,14除以5,余数仍为0,1,2,3,4;可以预见,再往下推理,余数仍然逃不出0,1,2,3,4这5个数的范围.这就是说,任一整数除以5,其余数只有5种可能.2一般地说,任一整数除以正整数n,其余数有且只有0,1,2,…,n-1共n种可能.特别提醒,余数必须是自然数而且比除数要小.即在式子中,必定有0≤r<a.2.同余问题2.写出100以内除以15余数是5的所有整数.【解析】根据公式b=15a+5.依次令a=0,1,2,3,4,5,6得:b=5,20,35,50,65,80,95.同余的字面含义就是余数相等.定义1:如果两个整数,ab,除以另一个整数c所得余数相等,就称这两个整数关于除数c同余.(在一些关于整除研究的书籍里,用符号mod表示同余.例如20≡35(mod15),表示20,35这两个整数除以15所得余数相等,它们都是5.)3.整数按同余分类问题3.证明:任意3个连续正整数之和一定是3的倍数【证明】将公式具体写为:b=3k+r.这里0≤r<3,且r为整数,∴r=0,1或2.于是所有整数按此同余可分为3类,即3k,3k+1和3k+2.也就是任意3个连续整数,有且仅有3种写法:(1)3k,3k+1,3k+2,其和为9k+3;(2)3k-1,3k,3k+1,其和为9k;(3)3k-2,3k-1,3k,其和为9k-3.无论哪种情况,其和均能为3整除,3所以,任意3个连续正整数之和一定是3的倍数评注:一般地,如果除数为n,∵0≤r<n,且r为整数,∴r=0,1,2,…,n-1那么所有整数可分为n类,即nk,nk+1,nk+2,…,nk+(n-1).事实上,整数分为奇数与偶数,也还是依照公式按同余分类.此时b=2k+r,且只有r=0与1.4.整除问题4.证明999999能被13整除.【解析】∵999999=999×1001,而1001=13×11×7即999999=999×13×11×7,等式右边含有因数13,故999999必能为13整除.定义2.如果整数b除以整数a没有剩余(即在式中,余数r=0),则称整数a能为整数b整除.定义3.如果整数b能为整数a整除,则称b为a的倍数,a为b的约数(或因数)如果a是质数,则称a为b的质因数.问题5.写出999的所有因数,并指出哪些是质因数【解析】999=3×3×3×37.故999的所有约数为1,3,3×3=9,3×3×3=27,37,3×37=111,9×37=333,999.共计8个.在999的所有约数中,只有3与37是质因数.注意1既不是质数,也不是合数.所以以上因数中,1不能称为质因数.定义4.任一整数必定有1和本身两个约数,称它们为该整数的当然约数.5.最大公约数与最小公倍数.4问题5.写出36与45的所有公约数与公倍数【解析】36的所有约数是1,2,3,4,6,9,12,18,36,45的所有约数是1,3,5,9,15,45.其中1,3,9既是36的约数.又是45的约数.所以1,3,9都是36与45的公约数.其中9是它们公约数中最大的,故称9为36与45的最大公约数.36的倍数依次为36,72,108,144,180,…45的倍数依次为45,90,135,180,….其中180既是36的倍数,又是45的倍数,故称为36与45的公倍数.这两个数的公倍数还有360,540,720,1440,…等无穷多个.但其中180是最小的,所以称180是36与45的最小公倍数.定义5.几个整数的公约数中最大的一个,称为最大公约数;几个整数公倍数中最小的一个叫做最小公倍数.6.互质整数问题6.25与16有公约数吗?为什么?【解析】24255,162∴25与16除1以外,再无其他公约数.定义6.两个整数的公约数除1以外,再无其他,则称这两个整数互质.反之,如果整数ab与互质,那么它们的最大公约数是1,而最小公倍数为ab.特别注意:整数的互质是没有传递性的.例如4与5互质,5与6也互质,由此并不能推出4与6也互质.事实上,4与6存在不是1的公约数2,所以它们不互质.以上我们对公式进行了6个方面的分析.其中最需要掌握,也是最难的重点知识就是“同余”,这得从孙子问题说起.(二)从“孙子问题”到孙子定理51.什么是“孙子问题”?“孙子问题”源于我国古代流传下来的《孙子算经》,它是世界级的名题.原文是:“今有物不知其数,三三数之余二,五五数之余三,七七数之余二,问物几何?”①注意到3,5,7都是质数.“孙子问题”的实质是:求一个整数N,使它同时满足除以3余2,除以5余3,除以7余2.假如只需求出这个“孙子问题”的一个答案,倒也简单:既是这些物品数以3与7除之都余2,那么它最少有3×7+2=23(件)注意到23正好满足除以5余3,所以所求物品的数量,最少有23件.可是,23不是本题的唯一解,如果再加上3,5,7的公倍数105的任意整数倍,即得到这个孙子问题的通解是N=105k+23(※)其中k为非负整数,当k=0,1,2,3…时依次得23,128,233.338,…等,它们都是这个孙子问题的解.各位请看:这个公式(1)是不是我们前面提到的带余除法的基本公式?我国古人将孙子问题的解法浓缩为如下四句话;三人同行七十稀,五树梅花廿一枝。七子团圆正半月,除百零五便得知。‘三人同行七十稀’,说的是70能够被5与7整除,但是被3除余1;‘五树梅花廿一支’,是说21是3与7的倍数,但被5除余1;‘七子团圆正半月’,是指15能够被3与5除尽,但被7除余1.这3句隐藏着孙子问题的正规解法是:将70二倍得140,这时它还是5与7的倍数,但符合被3除余2;6将21三倍得63,这时它还是3与7的倍数,但符合被5除余3;将15二倍得30,这时它还是3与5的倍数,但符合被7除余2。接着将所得3数相加,有140+63+30=233.这个数同时满足被3与7除余2,被5除余3。‘除百零五便得知’是说3×5×7=105,将233加上或减去105的倍数,所得23,128,338…等都是符合孙子问题的答案。2.孙子问题的现代解法各位如果对公式(※)的来源还有所疑虑的话,以下我们再用现代的方法给于推证:设所求物品数为x,由于x分别以3,7除之都余2,∴x=21m+2(m为非负整数)(1)由于x以5除之余3,∴x=5n+3(n为非负整数)(2)式子(1)与(2)表示同一个数,∴5n+3=21m+2将n用m的代数式表示:2111455mmnm为保证m,n为正整数,只能取51mk(k为非负整数)代入(1)即得:x=105k+23(k为非负整数)(3)所以(3),也就是(※)式即为孙子问题的通解.3.什么是孙子定理?将前述孙子问题一般化:已知123,,mmm是两两互质的正整数,求最小正整数N,使它被123,,mmm除所得余数分别为123,,rrr。7将这个问题再一般化:已知123,,,nmmmm是两两互质的正整数,求最小正整数N,使它被123,,,nmmmm除所得余数分别为123,,,nrrrr.《孙子算经》中已经证明,符合上述条件的最小正整数N一定存在,这个结论及其证明方法就是孙子定理,它被西方称之为“中国剩余定理”.需要提到的是:我国南宋时期的秦九韶对这个问题给出了更为科学且详尽的解法,他的方法被称为“大衍求一术”,他的成果比之西方的欧拉同样的成果要早500多年.孙子类问题频频出现于当今的各类数学竞赛与“小升初”等试题之中.到底孙子定理的解法,思想有多厉害,请看:(三)方法对头,势如破竹.为说明问题方便,我们约定.每一个符合公式baqr的式子都叫做一个剩余条件,而参与运算的一切字母,,,abqr等都是整数.孙子定理的实质是说,无论给于多少剩余条件,则符合所有这些条件的最小整数一定存在且有办法求出.当然,我们在实际解决问题时,可以运用更简单明了的现代方法.【例1】(1986.华罗庚金杯赛初赛,9题)有一个整数,除300,262,205后得到相同的余数,这个整数是几?【解析】设这个整数为x,分别去除300,262,205后所得余数为r,那么11221333003821926295519205kxrkkxkxrkkxkxr8最后两个式子的因数中,只有19是相同的,可知这个整数为19.评注.题设3数为x整除后同余,所以它们两两求差后必定是x的倍数,只需将这些差分解质因数即可.【例2】(1986.华罗庚金杯赛复赛,5题)有一个数,除以3余数是2,除以4余数是1.那么这个数除以12的余数是几?【解析1】满足除以3余数是2的数有5,8,11,14,17,…满足除以4余数是1的数有5,9,13,17,…其中5,17等既满足除以3余2,又满足除以4余1,而它们除以12的余数都是5,故满足题设条件的数除以12的余数是5.【解析2】设这个数为x,依题意有:x=3m+2或x=4n+1(其中m,n为正整数)命4113m24n133nnmn可见,当n=3k+1(k为正整数)时,m=4k+1也是正整数.此时x=12k+5故x除以12的余数是5.评注:解法1虽然简单,但理论推理较差,说服力不够强.而解法2则是按照题根的思路去做.道理清晰简明.【例3】(第7届全国数学大赛小五A卷.11题)789,1080,1468除以自然数A(A>1),所得的余数都相等,那么A=【解析】这3个数分别除以A后同余,故只需两两求出其差后分解质因数∵1080-789=291=3×9791468-1080=388=4×97.故所求整数A=97.【例4】(第3届全国数学大赛小六B卷.8题)一筐苹果,三三数之余一,四四数之余三,,五五数之不足1,这筐苹果最少有个【解析】设这筐苹果共有N个.依题意;N=3m+1=4n+3=5p-1.由323m14n34mn,显然46mk符合条件.此时N=3(4k+6)+1=12k+19.由1220212k19.512455kkppk显然k=5s都符合条件,此时N=12×5s+19=60s+19.取r=0,则N的最小值为19.评注.本题的剩余条件是3个.我们的办法是首先处理其中两个,得到合理结果后再继续处理另外一个.这种方法,类似于解方程组中的消元.【例5】(第4届全国数学大赛初赛小六A卷.10题)有一类数,它加上5能被9整除,它减去5能被7整除,在这类数中,由小到大排列,则第18个数是【解析】用x表示这类数,那么597109575579xmnmnmxn显然95nk时m为整数,此时x=7(9k+5)+5=63k+40.K=0时,11840;17,6317401111xkx时.即所求第18个数是1111.根据孙子定理,既然符合所给剩余条件的最小正整数可以求出,那么以后的任10意一个也就不在话下.【例6】(第5届全国数学大赛初赛小六A卷.11题)有若干名学生搬一堆杂志,若每人搬x捆,则剩下20捆未搬走;若每人搬9捆,则最后一名学生只搬6捆.一共有名学生.【解析】设一共有n名学生.依题意:23209169nxnxn,x,n均为
本文标题:一个题根从小学讲到高中从带余除法到中国剩余定理
链接地址:https://www.777doc.com/doc-2812190 .html