五年级数学竞赛第9讲同余VIP

第九讲 同余（一）我们已经学过整除的概念和带余数的除法：被除数=除数商+余数。在生活中，人们也经常关心“余数”，让我们看一个问题：2015年12月1日是星期二，问20年后的12月1日是星期几？由于每年有365天，20年里有20365=7300天，但每4年有一个闰年，20年里有5个闰年，所以20年有7305天。21cnjy7305=71043+4，说明20年中有1043周，外加4天，我们关心的其实不是20年中有多少周，而是“外加的4天”（换句话说，关心的不是商，而是余数），因此20年后的12月1日是应该是星期六。www-2-1-cnjy-com再看一个题目：一个奇数去除288和510所得的两个余数相同且都为29，求这个余数。如果从“被除数=除数商+余数”这个式子出发，必有“被除数余数=除数商”，可以知道28829和51029都是除数的倍数，即259和481都是除数的倍数。或者说除数是259和481的公约数。2-1-c-n-j-y用辗转相除法求259和481的最大公约数：481=2591+222；259=2221+37；222=376. 所以37双481和259的最大公约数。即37为我们要求的这个除数。验证一下：288=377+29；510=3713+29。结果是正确的。换一个角度考虑：由于288和510被同一个奇数除所得得余数相同，那么510和288的差就一定是这个奇数的倍数（求差时，相同的余数被减掉了）。【来源：21世纪教育网】因为510288=222=2337所求的奇数是222的奇数约数，只可能是37或111。但510=1114+66；288=1112+66。余数虽然相同但不是29，所以111不能是所求的奇数。而510=3713+29；288=377+29，所以37为所求的奇数。一同余的概念像510和288这两个数，被37除所得的余数相同（都是29），我们称510和288对于“模”37同余。【来源：21cnj*y.co*m】“对于模37同余”就是指被37除所得的余数相同，记为510288（mod37），这里mod37读作“模37”，“”读作“同余于”。【版权所有：21教育】一般地，两个整数a和b，除以一个大于1的自然数n所得的余数相同，就称a和b对于模n同余或a和b在模n下同余，记为ab(mod n)，有时也可以简读作a与b同余，这时只是未将模n读出而已，很明显一谈到同余总是与模有关。21教育名师原创作品很容易看到，所有的偶数在模2下彼此同余，所有的奇数在模2下也是彼此同余。这里实际上是用2来将整数分成了两类，一类被2整除（余数为0），另一类被2除余数为1。偶数：0、2、4、6、2k、；奇数1、3、5、7、2k+1、。如果用4来将整数分类，由于余数可以为0、1、2、3共四种，因此可以分为四类：0、4、8、12、4k、；1、5、9、4k+1、；2、6、10、4k+2、；3、7、11、4k+3、。同一类的数被4除的余数是相同的，也就是说在模4下同余。如816（mod4）；517（mod4）；214（mod4）；610（mod4）。21*cnjy*com因此对于每月的1号、8号、15号、22号、28号来说，1号是星期几，其他几天也是星期几。二同余的几条简单的性质性质1：任何整数都和自己同余，（这条性质称为自反性）aa（mod n）；性质2：甲、乙两个整数，如果甲和乙同余，那么乙和甲也同余。（这条称为对称性）若ab（mod n），则ba（mod n）。性质3：甲、乙、丙三个整数，如果甲和乙同余，乙和丙同余，那么甲和丙也同余。（这条称为传递性）。若ab（mod n），bc（mod n），则ac（mod n）。性质4：甲和乙同余，丙和丁同余，那么甲和丙的和与乙和丁的和一定同余（这条称为可加性）。甲和丙的差与乙和丁的差一定同余（这条称为可减性）。甲和丙的乘积与乙和丁的乘积一定同余（这条称为可乘性）。若ab（mod n），cd（mod n），则a+cb+d（mod n），acbd（mod n），acbd（mod n）。特别是当ab（mod n），c=d时，上面的式子也成立，写作，则a+cb+c（mod n），acbd（mod n），acbc（mod n）。性质5：甲和乙同余，那么甲和乙的同次乘方的结果仍然同余。若ab（mod n），则ambm（mod n）。以上的各条性质和等式的性质非常相似，不过同余式终究不是等式，并不是等式的各种性质都能移到同余式中来使用。注意同余式中不能随便使用同除性，即在同余式acbc（mod n）两端，如果同除以c之后可能不同余。例如106（mod 4），两边同除以2，会得到53（mod 4），这是错误的。例1求4373091993被7除的余数。解：可以将4373091993先计算出来，再用7来除，得到余数。但是计算量比较大。用同余来计算：4373 （mod 7）；3091 （mod 7）；19935 （mod 7）；利用同余式的可乘性，将三式相乘得4373091993315 （mod 7）15（mod 7）1 （mod 7），所以4373091993被7除的余数是1。例270个数排成一行，除了两头的两个数之外，每个数的三倍恰好等于它两边两个数的和，这一行最左边的几个数是这样的：0、1、3、8、21、，问这一行最右边的一个数被6除的余数是多少？解：如果将这70个数都写出来，再用6去除最右边的数，当然可以，但工作量比较大。本题中没有要求算出最右边的数，仅要求算出这个数被6除的余数。根据70个数组成的规律：中间一个数的三倍是它两边数的和。（除两头的两个数）那么中间这个数被6除的余数的3倍与两边两数被6除的余数之和再被6除的余数应该相同（即在模6下同余）。将0、1、3、8、21、55、被6除的余数依次写出来为0、1、3、2、3、1、，仔细观察这串余数，中间数的三倍与两边两数之和在模6下同余（被6除的余数相同）。因此用70个数中每个数被6除的余数组成的新数串来代替原数串，不会影响题目的要求。这样工作量小多了。写新数串的工作量小了。让我们再来观察新数串是否有一定的规律。将新数串多些几个数看看：0、1、3、2、3、1、0、5、3、4、3、5、0、1、3、2、3，。可以看出前12个数一段，将出现重复。70个数的前5段共60个数，第六段的第10个数是4，这就是原来数串中第70个数被6除的余数。例3求被7除的余数。解：由于这个数字太大，真正除工作量太大，不过可以试一下是否有规律。试着除一下，发现111111可以被7整除，这样可以将被除数从高位开始六位一段分割一下。2015=3356+5，于是最后一段有5个1，111117=15872，所以原数被7除余2.例4求被6除的余数。解：与上题比较，我们可以尝试用竖式除一下看看规律。即除第一个1以外，每三位一段，1111111被6除余1，又2014=3671+1，所以原数除到最后是剩下11，116=15。所以原数被6除的余数为5.三弃九法在进行计算时，要求准确无误，可是当数字较大或运算复杂时，容易出现错误，这就要求我们有较简便的办法判断是否出错，如能迅速认定计算有误将便于改正。如算得427839682=169759894，这个式子一看就知道不正确，因为末位数字8与2相乘，末位数字不可能是4。这种办法称为末位检验法。21*cnjy*com但如果计算得到427839682=169759896，从末位看不出问题来，不敢确定计算有无错误。在“同余的几条简单性质”的例题中，我们曾计算三个数的乘积4373091993被7除的余数，若改为计算4373091993被9除的余数，根据同余的性质可以分别计算437、309、1993被9除的余数，再求余数之积被9除的余数。【出处：21教育名师】437(4+3+7) (mod 9)5(mod 9)；309(3+0+9) (mod 9)3(mod 9)；1993(1+9+9+3) (mod 9)4(mod 9)。4373091993534(mod 9)60(mod 9)6(mod 9)。所以4373091993被9除余数是6.由于被9除的余数，只需计算数字和被9除的余数，因而可以用被9除的余数来检验计算的错误情况。如计算得427839682=169759896，用末位检验看不出问题，若计算正确，那么两端被9除的余数也应该相等。若两端被9除的余数不同，则一定是计算出了问题。由4278(4+2+7+8) (mod 9)3(mod 9)；39682(3+9+6+8+2) (mod 9)1(mod 9)，所以左边被9除的余数是3。而右边169759896(1+6+9+7+5+9+8+9+6) (mod 9)6。所以计算一定有问题。以上方法称为弃九法。不过应该注意，用弃九法可以发现问题，但是如果弃九法没有找出错误却不能保证计算一定正确。21如果是除法，可以转化为乘法来检验。例5用弃九法检验4651875869762=47653是否可能正确。解：转化为检验乘法976247653=465187586。9762(9+7+6+2)(mod 9)6(mod 9)，47653(4+7+6+5+3) (mod 9)7(mod 9)，所以97624765367(mod 9)42(mod 9)6(mod 9)，465187586(4+6+5+1+8+7+5+8+6)(mod 9)5(mod 9)，所以976247653 465187586，465187586976247653。练 习 题1求169411611被7除所得的余数。解：162(mod 7)，9413(mod 7)，16111(mod 7)，所以169411611231(mod 7) 6(mod 7)。所得的余数是6.2求被41除所得的余数。解：试除得1111141=271，对于，从最高位开始，每5个1分一段，可以得到403段，最后剩余1个1，这就是所得的余数。3用弃九法检验乘法54839117=49888511是否可能正确。解：5483(5+4+8+3)(mod 9)2(mod 9)，91170(mod 9)，所以548391170(mod 9)，49888511(4+9+8+8+8+5+1+1)8(mod 9)，用弃九法知道计算不正确。4用弃九法检验除法12264522683=334是否可能正确。解：2683(2+6+8+3) (mod 9)1(mod 9)，3341(mod 9)，而1226452(1+2+2+6+4+5+2) (mod 9)4(mod 9)，用弃九法知道计算不正确。5乘法算式314592653=2910 93995的横线处漏写了一个数字，你能以最快的办法补出吗？21世纪*教育网解：31454(mod 9)，926537(mod 9)，所以3145926531(mod 9)，设2910 93995的横线处填写的是a，即2910a93995(2+9+1+0+a+9+3+9+9+5)(mod 9)=a+2(mod 9)，所以a=8.613511、13903、14589被自然数m除所得的余数相同，问m的最大值是多少？解：1390313511=392，1458913903=686，用辗转相除法求392和686的最大公约数。686=1392+294， 392=1294+98， 294=398， 所以392与686的最大公约数是98。即m的值是98.7分别求出123123+456456+789789被3除和被9除的余数。解：1230(mod 3)，4560(mod 3)，7890(mod 3)，所以123123+456456+789789能被3整除，余数为0，1236(mod 9)，62=360(mod 9)，所以1231230(mod 9)，4566(mod 9)，所以4564560(mod 9)，7896(mod 9)，所以7897890(mod 9)，所以123123+456456+789789被9除的余数为0.8将奇数按下列图排好，各列分别用A、B、C、D、E、F、G作为代表，问2015所在的列以那个字母作为代表？ABCDEFG1357911232119171513252729313335474543413937495153555759解：每行有6个奇数，从1开始数，到2015是第1008个奇数，1008=6168，所以2015在第168行上，按照规律，双数行的排列是从F到A的顺序排列，所以2015排在字母A所在的列。9如果2和3均不能整除a和b，那么必有a2b2(mod 24)证明：由题意2和3均不能整除a和b，即a，b都是奇数，且不能被3整除，那么它们被3除的余数为1或2，即a1(mod 3)，或a2(mod 3)，若a1(mod 3)，则a21(mod 3)；若a2(mod 3)，则a21(mod 3)，即对于符合题意条件的a，b一定都满足a21(mod 3)，b21(mod 3)，所以a2b20(mod 3)。即a2b2能被3整除。再看a，b被8除的余数，由题意知a1(mod 8)或a=5(mod 8)或a=7(mod 8)，对于a1(mod 8)，则a21(mod 8)；对于a5(mod 8)，则a225(mod 8)1(