应用同余解题.doc

(完整word)应用同余解题应用同余解题在五年级我们已初步学习了同余的有关知识同余在解答竞赛题中有着广泛的应用在这一讲中，我们将深入理解同余的概念和性质,悟出它的一些运用技巧和方法例1 a除以5余1，b除以5余4，如果3ab，那么3ab除以5余几？分析 与余数有关的问题考虑用同余式可以使解题简便解：a1（mod5),3a3（mod 5），或者3a8（mod 5)（1)又 b4（mod 5），(2)（1)（2）得:3ab844（mod 5）因此，3ab除以5余4例2 若a为自然数，证明10（a1985a1949）分析 如果换一种方式表达，所要证明的即是要证a1985与a1949个位数字相同用对于模10两数同余来解，可以使解题过程简化证明：a1985a44961a（mod 10),a1949a44971a（mod 10),a1985a1949aa0(mod 10）即10（a1985a1949)说明:这里用到一个事实：对于任何自然数a，a5与a的个位数字相同 由能被8、9整除的特征，得由(2)得 y2(mod 8)因0y9且y是整数y2把y2代入（1)得x67920（mod 9）x3（mod 9）由x是一位整数得:x3所求五位数是36792分析 设 n9商r，那么9（nr）,根据 nr商9，以及nr的个位数字，可推算出商的个位数字抓住“一个整数与它的各位数字之和对于模9同余”这性质，可以很快的化大数为小数191920224（mod 9)，9（n4)，即n49商，又n4的个位数字是5，n被9除所得的商的个位数字是5例5 设2n1是质数,证明：12,22，n2被2n1除所得的余数各不相同分析 这道题肯定不可能通过各数被2n1除去求余数那么我们可以考虑从反面入手，假设存在两个相同的余数的话，就会发生矛盾而中间的推导是步步有根据的，所以发生矛盾的原因是假设不合理从而说明假设不成立，因此原来的结论是正确的证明：假设有两个数a、b，（ab，设ba，且1an，1bn），它们的平方a2，b2被2n1除余数相同那么，由同余定义得a2b20（mod(2n1）即（ab)（ab）0（mod（2n1)）,由于2n1是质数ab0（mod（2n1)）或ab0（mod（2n1）由于ab，ab均小于2n1且大于零，可知，ab与2n1互质,ab也与 2n1互质即ab与ab都不能被2n1整除产生矛盾，原题得证说明：这里用到一个重要的事实：如果AB0（modp），p是质数,那么A或B中至少有一个模p为零p是质数这一条件不能少，否则不能成 问:a除以13所得余数是几？解：用试除方法可知：13191919191923838，而33837，即1919个“1919”有3838个“19”，三组三组取走“19”后还剩下一组a19（mod 13)a6(mod 13）即a除以13余数是6例7 求被3除余2，被5除余3，被7除余5的最小三位数解：设x为所求数,由题意（3）即x7k5(k是整数）代入（2）得7k53（mod 5)，2k3（mod 5),2k8(mod 5） k4（mod 5），即 k5m4（m是整数）x7k57（5m4)535m33,上式代入（1）得:35m332（mod 3），2m2（mod 3），m1（mod 3)，即m3t1（t是整数）x35m3335（3t1)33105t68，当t1时，x173所求的最小三位数为 173例8 给出12个彼此不同的两位数，证明：由它们中一定可以选出两个数，它们的差是两个相同数字组成的两位数分析 证这道题要考虑到以下三点两位数的数码相同时，它一定能被11整除遇到数是任意的，需排个序,这样讨论表述起来比较方便用12个数中最大的数依次地分别减去其余11个数可得到11个差若差中有相同数码组成的两位数，问题得证；若差中没有合条件的两位数，这时这11个（差）数各自除以11，所得余数只可能在1，2，3，10中，必有两个差数的余数相同,考虑用余数造抽屉解题证明：设12个两位数从小到大排列为：10a1a2a11a1299，用a12分别减去其余的数，得差：b1a12a1,b2a12a2,，b11a12a11若上面11个差中有某个差bi能被11整除，即11（a12ai），那么已证出数a12与ai的差bi是两个相同数码组成的两位数若这11个差均不能被11整除，则按不能被11整除的余数造10个抽屉，余数相同者归入同一抽屉，根据抽屉原理，11个差数中，一定存在两数bm、bn对于模11同余,即：bmbn0（mod 11），即（a12am）（a12an)0(mod 11),即anam0（mod 11)，即11(anam）,即差anam是一个由相同数码组成的两位数综合(1）、（2）问题得证说明:这道题的证明用到了将数按被11除的余数分类的思想一般地,任何一个整数a被自然数n除,余数只可能是0，1，2,，n1这n种情况,这样我们可以利用余数将整数分为几类，如：整数按除以2余1还是0，分为奇数和偶数又如，整数除以3，余数只能是0,1,2这三种情况,我们可以把所有整数按除以3后的余数分三类,即 3k,3k1，3k2,（k是整数）这种利用余数分类思想,是重要的数学思想方法,它可以使研究问题时搜索的范围大大缩小例9 试证不小于5的质数的平方与1的差必能被24整除证明：质数中仅有一个偶数2，不小于5的质数是奇数又不小于5的自然数按除以6所得的余数可分为6类：6n，6n1,6n2,6n3，6n4,6n5，（n是自然数），其中6n,6n2，6n4都是偶数，又36n3不小于5的质数只可能是6n1,6n5又自然数除以6余数是5的这类数换一记法是:6n1，(不小于5的质数）21（6n1）2136n212n12n（3n1）,这里n与（3n1）奇偶性不同，其中定有一个偶数，2n（3n1），2412n（3n1）结论成立说明:按同余类造抽屉是解竞赛题的常用方法例10 任给七个不同的整数，证明其中必有两个数，其和或差是10的倍数分析 首先考虑什么样的两个整数的和或差可以被10整除设两个整数a、 b，若ab（mod 10),则10（ab）；若 ar（mod 10），而 b10r（mod 10），则 10(ab），只有这两种情况但是如果按整数除以10的余数造抽屉,就有十个抽屉,对于已知条件中给定的七个数无法应用抽屉原理，所以要考虑如何造六个抽屉根据首先考虑的两个整数被10除的两种情况,可以把余数之和等于10的并成一类，这样分为：10k、 10k1、 10k2、 10k3、10k4、 10k5六类,恰好构造六个抽屉，再应用抽屉原理可解此题证明:根据整数nr（mod 10)构造六个抽屉如下：r0的数；r5的数;r1或9的数；r2或8的数；r3或7的数;r4或6的数这样任给定的七个整数按照除以10的余数r，放入六个抽屉中，必有一个抽屉中至少有两个数这两数的和或差必是10的倍数