应用同余解题.doc

(完整word)应用同余解题
应用同余解题
　　在五年级我们已初步学习了同余的有关知识．同余在解答竞赛题中有着广泛的应用．在这一讲中，我们将深入理解同余的概念和性质,悟出它的一些运用技巧和方法．
　　例1 a除以5余1，b除以5余4，如果3a＞b，那么3a－b除以5余几？
　　分析 与余数有关的问题考虑用同余式可以使解题简便．
　　解：∵a≡1（mod5),
　　∴3a≡3（mod 5），
　　或者3a≡8（mod 5)．（1)
　　又∵ b≡4（mod 5），(2)
　　∴（1)－（2）得:
　　3a－b≡8－4≡4（mod 5）．
　　因此，3a－b除以5余4．
　　例2 若a为自然数，证明10│（a1985－a1949）．
　　分析 如果换一种方式表达，所要证明的即是要证a1985与a1949个位数字相同．用对于模10两数同余来解，可以使解题过程简化．
　　证明：∵a1985＝a4×496＋1≡a（mod 10),
　　a1949＝a4×497＋1≡a（mod 10),
　　∴a1985－a1949≡a－a≡0(mod 10）．
　　即10│（a1985－a1949)．
　　说明:这里用到一个事实：对于任何自然数a，a5与a的个位数字相同．

　　由能被8、9整除的特征，得

　　由(2)得 y≡2(mod 8)
　　因0≤y〈9且y是整数
　　∴y＝2．
　　把y＝2代入（1)得
　　x＋6＋7＋9＋2≡0（mod 9）
　　∴x≡3（mod 9）．
　　由x是一位整数得:x＝3．
　　∴所求五位数是36792．

　　分析 ①设 n÷9＝商…r，那么9│（n－r）,根据 n－r＝商×9，以及n－r的个位数字，可推算出商的个位数字．
　　②抓住“一个整数与它的各位数字之和对于模9同余”这性质，可以很快的化大数为小数．
　　≡1919×20≡2×2≡4（mod 9)，
　　　　∴9│（n－4)，即n－4＝9×商，
　　　又∵n－4的个位数字是5，
　　　　∴n被9除所得的商的个位数字是5．
　　例5 设2n＋1是质数,证明：12,22，…，n2被2n＋1除所得的余数各不相同．
　　分析 这道题肯定不可能通过各数被2n＋1除去求余数．那么我们可以考虑从反面入手，假设存在两个相同的余数的话，就会发生矛盾．而中间的推导是步步有根据的，所以发生矛盾的原因是假设不合理．从而说明假设不成立，因此原来的结论是正确的．
　　证明：假设有两个数a、b，（a≠b，设b〈a，且1≤a≤n，1≤b≤n），它们的平方a2，b2被2n＋1除余数相同．
　　那么，由同余定义得a2－b2≡0（mod(2n＋1））．
　　即（a＋b)（a－b）≡0（mod（2n＋1)）,由于2n＋1是质数．
　　∴a＋b≡0（mod（2n＋1)）或a－b≡0（mod（2n＋1））．
　　由于a＋b，a－b均小于2n＋1且大于零，
　　可知，a＋b与2n＋1互质,a－b也与 2n＋1互质．
　　即a＋b与a－b都不能被2n＋1整除．
　　产生矛盾，∴原题得证．
　　说明：这里用到一个重要的事实：如果A·B≡0（modp），p是质数,那么A或B中至少有一个模p为零．p是质数这一条件不能少，否则不能成

　　问:a除以13所得余数是几？
　　解：用试除方法可知：13│191919．
　　∵1919×2＝3838，而3│3837，

　　即1919个“1919”有3838个“19”，三组三组取走“19”后还剩下一组．
　　∴a≡19（mod 13)．
　　∴a≡6(mod 13）．
　　即a除以13余数是6．
　　例7 求被3除余2，被5除余3，被7除余5的最小三位数．
　　解：设x为所求数,
　　由题意

　　（3）即x＝7k＋5(k是整数）．代入（2）得
　　7k＋5≡3（mod 5)，
　　∴2k≡3（mod 5),
　　　2k≡8(mod 5）．
　　∴ k≡4（mod 5），即 k＝5m＋4（m是整数）．
　　∴x＝7k＋5＝7（5m＋4)＋5＝35m＋33,
　　上式代入（1）得:
　　35m＋33≡2（mod 3），
　　2m≡2（mod 3），
　　∴m≡1（mod 3)，即m＝3t＋1（t是整数）．
　　∴x＝35m＋33＝35（3t＋1)＋33＝105t＋68，
　　当t＝1时，x＝173．
　　∴所求的最小三位数为 173．
　　例8 给出12个彼此不同的两位数，证明：由它们中一定可以选出两个数，它们的差是两个相同数字组成的两位数．
　　分析 证这道题要考虑到以下三点．
　　①两位数的数码相同时，它一定能被11整除．
　　②遇到数是任意的，需排个序,这样讨论表述起来比较方便．
　　③用12个数中最大的数依次地分别减去其余11个数可得到11个差．若差中有相同数码组成的两位数，问题得证；若差中没有合条件的两位数，这时这11个（差）数各自除以11，所得余数只可能在｛1，2，3，…，10｝中，必有两个差数的余数相同,考虑用余数造抽屉解题．
　　证明：设12个两位数从小到大排列为：
　　10≤a1＜a2＜…＜a11＜a12≤99，
　　用a12分别减去其余的数，得差：
　　b1＝a12－a1,b2＝a12－a2,…，b11＝a12－a11．
　　①若上面11个差中有某个差bi能被11整除，即11│（a12－ai），那么已证出数a12与ai的差bi是两个相同数码组成的两位数．
　　②若这11个差均不能被11整除，则按不能被11整除的余数造10个抽屉，余数相同者归入同一抽屉，根据抽屉原理，11个差数中，一定存在两数bm、bn对于模11同余,即：bm－bn≡0（mod 11），
　　即（a12－am）－（a12－an)≡0(mod 11),
　　即an－am≡0（mod 11)，
　　即11│(an－am）,
　　即差an－am是一个由相同数码组成的两位数．综合(1）、（2）问题得证．
　　说明:这道题的证明用到了将数按被11除的余数分类的思想．
　　一般地,任何一个整数a被自然数n除,余数只可能是0，1，2,…，n－1这n种情况,这样我们可以利用余数将整数分为几类，如：整数按除以2余1还是0，分为奇数和偶数．
　　又如，整数除以3，余数只能是0,1,2这三种情况,我们可以把所有整数按除以3后的余数分三类,即 3k,3k＋1，3k＋2,（k是整数）．
　　这种利用余数分类思想,是重要的数学思想方法,它可以使研究问题时搜索的范围大大缩小．
　　例9 试证不小于5的质数的平方与1的差必能被24整除．
　　证明：∵质数中仅有一个偶数2，
　　∴不小于5的质数是奇数．
　　又不小于5的自然数按除以6所得的余数可分为6类：6n，6n＋1,6n＋2,6n＋3，6n＋4,6n＋5，（n是自然数），
　　其中6n,6n＋2，6n＋4都是偶数，又3│6n＋3．
　　∴不小于5的质数只可能是6n＋1,6n＋5．
　　又自然数除以6余数是5的这类数换一记法是:6n－1，
　　∴(不小于5的质数）2－1＝（6n±1）2－1
　　＝36n2±12n＝12n（3n±1）,
　　这里n与（3n±1）奇偶性不同，其中定有一个偶数，
　　∴2│n（3n±1），
　　∴24│12n（3n±1）．
　　∴结论成立．
　　说明:按同余类造抽屉是解竞赛题的常用方法．
　　例10 任给七个不同的整数，证明其中必有两个数，其和或差是10的倍数．
　　分析 首先考虑什么样的两个整数的和或差可以被10整除．设两个整数a、 b，若a≡b（mod 10),则10│（a－b）；若 a≡r（mod 10），而 b≡10－r（mod 10），则 10│(a＋b），只有这两种情况．但是如果按整数除以10的余数造抽屉,就有十个抽屉,对于已知条件中给定的七个数无法应用抽屉原理，所以要考虑如何造六个抽屉．根据首先考虑的两个整数被10除的两种情况,可以把余数之和等于10的并成一类，这样分为：10k、 10k±1、 10k±2、 10k±3、10k±4、 10k±5六类,恰好构造六个抽屉，再应用抽屉原理可解此题．
　　证明:根据整数n≡r（mod 10)构造六个抽屉如下：
　　r＝0的数；r＝5的数;r＝1或9的数；r＝2或8的数；r＝3或7的数;r＝4或6的数．
　　这样任给定的七个整数按照除以10的余数r，放入六个抽屉中，必有一个抽屉中至少有两个数．这两数的和或差必是10的倍数．