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

1、 第九第九讲讲 同余（一）同余（一） 我们已经学过整除的概念和带余数的除法：被除数=除数商+余数。 在生活中，人们也经常关心“余数”，让我们看一个问题： 2015 年 12 月 1 日是星期二，问 20 年后的 12 月 1 日是星期几？ 由于每年有 365 天，20 年里有 20365=7300 天，但每 4 年有一个闰年，20 年里有 5 个闰年，所以 20 年有 7305 天。2 1 c n j y 7305=71043+4，说明 20 年中有 1043 周，外加 4 天，我们关心的其实不是 20 年中有 多少周，而是“外加的 4 天”（换句话说，关心的不是商，而是余数），因此 20 年

2、后的 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 为我们要

3、求的这个除数。 验证一下：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

4、这两个数，被 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 教

5、育名师原创作品 很容易看到，所有的偶数在模 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）；5 17（mod4）；214（mod4）；610（mod

6、4）。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：甲和乙同余，丙和丁同余，那么甲和丙的和与乙和丁的和一

7、定同余（这条称为 可加性）。甲和丙的差与乙和丁的差一定同余（这条称为可减性）。甲和丙的乘积与乙和丁 的乘积一定同余（这条称为可乘性）。 若 ab（mod n），cd（mod n），则 a+cb+d（mod n），acbd（mod n），a cbd（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）。 以上的各条性质和等式的性质非常相似， 不过同余式终究不是等式， 并不是等

8、式的各种 性质都能移到同余式中来使用。 注意同余式中不能随便使用同除性，即在同余式 acbc（mod n）两端，如果同除以 c 之后可能不同余。 例如 106（mod 4），两边同除以 2，会得到 53（mod 4），这是错误的。 例 1求 437 3091993 被 7 除的余数。 解：可以将 437 3091993 先计算出来，再用 7 来除，得到余数。但是计算量比较大。 用同余来计算： 4373 （mod 7）；3091 （mod 7）；19935 （mod 7）； 利用同余式的可乘性，将三式相乘得 4373091993315 （mod 7）15（mod 7）1 （mod 7）， 所以

9、437 3091993 被 7 除的余数是 1。 例 270 个数排成一行，除了两头的两个数之外，每个数的三倍恰好等于它两边两个数 的和，这一行最左边的几个数是这样的：0、1、3、8、21、，问这一行最右边的一个数 被 6 除的余数是多少？ 解：如果将这 70 个数都写出来，再用 6 去除最右边的数，当然可以，但工作量比较大。 本题中没有要求算出最右边的数，仅要求算出这个数被 6 除的余数。 根据 70 个数组成的规律：中间一个数的三倍是它两边数的和。（除两头的两个数） 那么中间这个数被6除的余数的3倍与两边两数被6除的余数之和再被6除的余数应该 相同（即在模 6 下同余）。 将 0、1、3、

10、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求

11、20151 1111 个 被 7 除的余数。 解：由于这个数字太大，真正除工作量太大，不过可以试一下是否有规律。 试着除一下，发现 111111 可以被 7 整除，这样可以将被除数从高位开始六位一段分割 一下。2015=3356+5，于是最后一段有 5 个 1，111117=15872， 所以原数被 7 除余 2. 例 4求 20151 1111 个 被 6 除的余数。 解：与上题比较，我们可以尝试用竖式除一下看看规律。 185185 6 111111111 6 51 48 31 30 11 6 51 48 31 30 1 即除第一个 1 以外，每三位一段，1111111 被 6 除余 1，又

12、 2014=3671+1， 所以原数除到最后是剩下 11，116=15。所以原数被 6 除的余数为 5. 三弃九法 在进行计算时，要求准确无误，可是当数字较大或运算复杂时，容易出现错误，这就要 求我们有较简便的办法判断是否出错，如能迅速认定计算有误将便于改正。 如算得 427839682=169759894，这个式子一看就知道不正确，因为末位数字 8 与 2 相 乘，末位数字不可能是 4。这种办法称为末位检验法。 21*cnjy*com 但如果计算得到 427839682=169759896，从末位看不出问题来，不敢确定计算有无错 误。 在“同余的几条简单性质”的例题中，我们曾计算三个数的乘积

13、 437 3091993 被 7 除的余数，若改为计算 437 3091993 被 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)。 437 3091993534(mod 9)60(mod 9)6(mod 9)。 所以 437 3091993 被 9 除余数是 6. 由于被 9 除的余数， 只需计算数字和被 9 除的余数， 因而可以

14、用被 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。所以计算一定有问题。 以上方法称为弃九法。不过应该注意，用弃九法可以发现问题，但是如果弃九法没有找 出错误却不能保证计算一定正确。 如

15、果是除法，可以转化为乘法来检验。 例 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)， 所以 9762476536 7(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

16、被 7 除所得的余数。 解：162(mod 7)，9413(mod 7)，16111(mod 7)， 所以 169411611231(mod 7) 6(mod 7)。 所得的余数是 6. 2求 20161 1111 个 被 41 除所得的余数。 解：试除得 1111141=271，对于 20161 1111 个 ， 从最高位开始，每 5 个 1 分一段，可以得到 403 段，最后剩余 1 个 1，这就是所得的余 数。 3用弃九法检验乘法 54839117=49888511 是否可能正确。 解：5483(5+4+8+3)(mod 9)2(mod 9)，91170(mod 9)， 所以 54839

17、1170(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(m

18、od 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

19、除和被 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 所在的 列以那个字母作为代表？www.21-cn-

20、 A B C D E F G 1 3 5 7 9 11 23 21 19 17 15 13 25 27 29 31 33 35 47 45 43 41 39 37 49 51 53 55 57 59 解：每行有 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 整

21、除， 那么它们被 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(mod 8)； 对于 a7(mo

22、d 8)，则 a249(mod 8)1(mod 8)； 所以 a2b20(mod 8)。即 a2b2能被 8 整除。 3 和 8 互质，所以即 a2b2能被 38=24 整除。即 a2b2(mod 24)。 10证明：形如 8k+7 的数不能表示为三个平方数的和。 证明：对于所有的偶数，可以表示为 2n(n 为整数)的形式， (2n)2=4n2，n20(mod 2)或 n21(mod 2)， 所以(2n)20(mod 8)或(2n)2=4(mod 8)， 对于所有的奇数，可以表示为 2m+1(m 为整数)的形式， (2m+1)2=4m2+4m+1=4m(m+1)+1，其中 m(m+1)一定可以

23、被 2 整除， 所以(2m+1)21(mod 8). 由题意知 8k+77(mod 8)， 如果三个数都是偶数， 则它们的平方和被 8 除的余数可能是 0+0+0=0、 0+0+4=4、 0+4+4 0(mod 8)、4+4+44(mod 8)，都不可能是 7.21 世纪教育网版权所有 如果是两个偶数一个奇数，则它们的平方和被 8 除的余数可能是 0+0+1=1、0+4+1=5、 4+4+11(mod 8)，也不可能是 7。21 教育网 如果是一个偶数两个奇数，则它们的平方和被 8 除的余数可能是 0+1+1=2 或 4+1+1=6， 不可能是 7.21 cn jy com 如果三个数都是奇数，则它们的平方和被 8 除的余数是 1+1+1=3，也不是 7. 综上所述，形如 8k+7 的数不能表示为三个平方数的和。