应用同余解题.doc

(完整word)应用同余解题(完整word)应用同余解题(完整word)应用同余解题应用同余解题在五年级我们已初步学习了同余的有关知识．同余在解答竞赛题中有着广泛的应用．在这一讲中，我们将深入理解同余的概念和性质,悟出它的一些运用技巧和方法．例1a除以5余1，b除以5余4，如果3a＞b，那么3a－b除以5余几？分析与余数有关的问题考虑用同余式可以使解题简便．解：∵a≡1（mod5),∴3a≡3（mod5），或者3a≡8（mod5)．（1)又∵b≡4（mod5），(2)∴（1)－（2）得:3a－b≡8－4≡4（mod5）．因此，3a－b除以5余4．例2若a为自然数，证明10│（a1985－a1949）．分析如果换一种方式表达，所要证明的即是要证a1985与a1949个位数字相同．用对于模10两数同余来解，可以使解题过程简化．证明：∵a1985＝a4×496＋1≡a（mod10),a1949＝a4×497＋1≡a（mod10),∴a1985－a1949≡a－a≡0(mod10）．即10│（a1985－a1949)．说明:这里用到一个事实：对于任何自然数a，a5与a的个位数字相同．由能被8、9整除的特征，得由(2)得y≡2(mod8)因0≤y〈9且y是整数∴y＝2．把y＝2代入（1)得x＋6＋7＋9＋2≡0（mod9）∴x≡3（mod9）．由x是一位整数得:x＝3．∴所求五位数是36792．分析①设n÷9＝商…r，那么9│（n－r）,根据n－r＝商×9，以及n－r的个位数字，可推算出商的个位数字．②抓住“一个整数与它的各位数字之和对于模9同余”这性质，可以很快的化大数为小数．≡1919×20≡2×2≡4（mod9)，∴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（mod13)．∴a≡6(mod13）．即a除以13余数是6．例7求被3除余2，被5除余3，被7除余5的最小三位数．解：设x为所求数,由题意（3）即x＝7k＋5(k是整数）．代入（2）得7k＋5≡3（mod5)，∴2k≡3（mod5),2k≡8(mod5）．∴k≡4（mod5），即k＝5m＋4（m是整数）．∴x＝7k＋5＝7（5m＋4)＋5＝35m＋33,上式代入（1）得:35m＋33≡2（mod3），2m≡2（mod3），∴m≡1（mod3)，即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是两个相同数