小学奥数—同余问题.doc

1、数论之同余问题余数问题是数论知识板块中另一个内容丰富， 题目难度较 大的知识体系，也是各大杯 赛小升初考试必考的奥数知识点，所以学好本 讲对于学生来说非常重要。许多孩子都接触过余数的有关问题，并有不少孩子 说“ 遇到余数的问题就基本晕菜了！”余数问题主要包括了带余除法的定义，三大余数定理（加法余数定理，乘法余数定理，和同余定理），及中国剩余定理和有关弃九法原理的应用。知识点拨：一、带余除法的定义及性质：一般地，如果 a 是整数，b 是整数（b0）,若有 ab=qr，也就是 abq r, 0r b；我 们称上面的除法算式为一个带余除法算式。这里：(1)当 时：我们称 a 可以被 b 整除，q 称

2、为 a 除以 b 的商或完全商0r(2)当 时：我们称 a 不可以被 b 整除，q 称为 a 除以 b 的商或不完全商一个完美的带余除法讲解模型:如图，这是一堆书，共有 a 本， 这个 a 就可以理解为被除数，现在要求按照 b 本一捆打包，那么 b 就是除数的角色， 经过打包后共打包了 c 捆，那么 这个 c 就是商，最后 还剩余 d 本， 这个 d 就是余数。这个图能够让学生清晰的明白带余除法算式中 4 个量的关系。并且可以看出余数一定要比除数小。二、三大余数定理：1.余数的加法定理a 与 b 的和除以 c 的余数，等于 a,b 分别除以 c 的余数之和，或这个和除以 c 的余数。例如：23

3、，16 除以 5 的余数分 别是 3 和 1，所以 23+16=39 除以 5 的余数等于 4，即两个余数的和 3+1.当余数的和比除数大时，所求的余数等于余数之和再除以 c 的余数。例如：23，19 除以 5 的余数分 别是 3 和 4，故 23+19=42 除以 5 的余数等于 3+4=7 除以 5 的余数，即 2.2.余数的乘法定理a 与 b 的乘积除以 c 的余数，等于 a,b 分别除以 c 的余数的积，或者这个积除以 c 所得的余数。例如：23，16 除以 5 的余数分 别是 3 和 1，所以 2316 除以 5 的余数等于 31=3。当余数的和比除数大时，所求的余数等于余数之 积再

4、除以 c 的余数。例如：23，19 除以 5 的余数分 别是 3 和 4，所以 2319 除以 5 的余数等于 34 除以 5 的余数，即 2.3.同余定理若两个整数 a、b 被自然数 m 除有相同的余数，那么称 a、b 对于模 m 同余，用式子表示为：ab ( mod m )，左边的式子叫做同余式。同余式读作：a 同余于 b，模 m。由同余的性 质，我们可以得到一个非常重要的推论：若两个数 a，b 除以同一个数 m 得到的余数相同， 则 a，b 的差一定能被 m 整除用式子表示为：如果有 ab ( mod m )，那么一定有 abmk,k 是整数，即 m|(ab)三、弃九法原理：在公元前 9

5、 世纪，有个印度数学家名叫花拉子米，写有一本花拉子米算术，他们在计算时通常是在一个铺有沙子的土板上进行，由于害怕以前的 计算结果丢 失而经常检验加法运算是否正确，他 们的检验方式是这样进行的：例如：检验算式 1234891267891028931234 除以 9 的余数为 11898 除以 9 的余数为 818922 除以 9 的余数为 4678967 除以 9 的余数为 7178902 除以 9 的余数为 0这些余数的和除以 9 的余数为 2而等式右边和除以 9 的余数为 3，那么上面 这个算式一定是 错的。上述检验方法恰好用到的就是我们前面所讲的余数的加法定理，即如果这个等式是正确的，那么

6、左 边几个加数除以 9 的余数的和再除以 9 的余数一定与等式右边和除以 9 的余数相同。而我们在求一个自然数除以 9 所得的余数时，常常不用去列除法竖式进行计算，只要 计算这个自然数的各个位数字之和除以 9 的余数就可以了，在算的 时候往往就是一个 9 一个 9 的找并且划去，所以 这种方法被称作“弃九法 ”。所以我们总结出弃九发原理：任何一个整数模 9 同余于它的各数位上数字之和。以后我们求一个整数被 9 除的余数，只要先 计算这个整数各数位上数字之和，再求这个和被 9 除的余数即可。利用十进制的这个特性，不仅 可以检验几个数相加， 对于检验 相乘、相除和乘方的结果对不对同样适用注意：弃九

7、法只能知道原题一定是错的或有可能正确，但不能保证一定正确。例如：检验算式 9+9=9 时，等式两 边的除以 9 的余数都是 0，但是显然算式是错误的但是反过来，如果一个算式一定是正确的，那么它的等式 2 两端一定满足弃九法的规律。这个思想往往可以帮助我们解决一些较复杂的算式迷问题。四、中国剩余定理：1.中国古代趣题：中国数学名著孙子算经里有这样的问题：“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？” 答曰： “二十三。 ”此类问题我们可以称为“物不知其数”类型，又被称为“韩信点兵”。韩信点兵又称为中国剩余定理，相 传汉高祖刘邦问大将军韩 信统御兵士多少， 韩信答

8、说，每 3 人一列余 1 人、5 人一列余 2 人、7 人一列余 4 人、13 人一列余 6 人。刘邦茫然而不知其数。 我们先考虑下列的问题：假设兵不满一万，每 5 人一列、 9 人一列、13 人一列、17 人一列都剩 3 人，则兵有多少？ 首先我们先求 5、9、13、17 之最小公倍数 9945（注：因为 5、9、13、17 为两两互质的整数，故其最小公倍数为这些数的积），然后再加 3，得 9948（人）。 孙子算经的作者及确实著作年代均不可考，不 过根据考证 ，著作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人 发现得比西方早，所以 这个 问题的推广及其解法，被称为中国剩余定

9、理。中国剩余定理（Chinese Remainder Theorem）在近代抽象代数学中占有一席非常重要的地位。2.核心思想和方法：对于这一类问题，我们有一套看似繁 琐但是一旦掌握便可一通百通的方法，下面我们就以孙子算经中的问题为例，分析此方法:今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？题目中我们可以知道，一个自然数分 别除以 3，5，7 后，得到三个余数分别为 2，3，2.那么我们首先构造一个数字，使得这个数字除以 3 余 1，并且 还是 5 和 7 的公倍数。先由 ，即 5 和 7 的最小公倍数出 发，先看 35 除以 3 余 2，不符合要求，那么就 继续

10、看 5 和 7573的“下一个”倍数 是否可以，很显然 70 除以 3 余 120类似的，我们再构造一个除以 5 余 1，同 时又是 3 和 7 的公倍数的数字，显然 21 可以符合要求。最后再构造除以 7 余 1，同时 又是 3，5 公倍数的数字，45 符合要求，那么所求的自然数可以 这样计算：，其中 k 是从 1 开始的自然数。20324,72,kk也就是说满足上述关系的数有无穷多，如果根据 实际情况 对数的范围加以限制，那么我 们就能找到所求的数。例如对上面的问题加上限制条件“满足上面条件最小的自然数”，那么我们可以计算 得到所求270312453,72如果加上限制条件“满足上面条件最小

11、的三位自然数”,我们只要对最小的 23 加上3,5,7即可，即 23+105=128。例题精讲：【模块一：带余除法的定义和性质】【例 1】 (第五届小学数学报竞赛决赛)用某自然数 去除 ，得到商是 46，余数是 ，求 和 a192rar【 因为 是 的 倍还多 ,得到 ，得 ，所以 ，192a46r192463.463143r【 (清华附中小升初分班考试) 甲、乙两数的和是 ，甲数除以乙数商 余 ，求甲、乙两数1082【 (法 1)因为 甲 乙 ，所以 甲 乙 乙 乙 乙 ；132321308则乙 ，甲 乙 108)8108(法 2)将余数先去掉变成整除性问题，利用倍数关系来做：从 中减掉 以

12、后， 就应当是082156乙数的 倍，所以得到乙数 ，甲数 )5621【 一个两位数除 310，余数是 37，求这样的两位数。【 本题为余数问题的基础题型，需要学生明白一个重要知识点，就是把余数问题-即“不整除问题”转化为整除问题。方法 为用被除数减去余数，即得到一个除数的倍数；或者是用被除数加上一个“除数与余数的差 ”，也可以得到一个除数的倍数。本题中 310-37=273，说明 273 是所求余数的倍数，而 273=3713，所求的两位数约数还要满足比37 大，符合条件的有 39，91.【例 2】 ( 年全国小学数学奥林匹克试题)有两个自然数相除，商是 ，余数是 ，已知被除数、203 17

13、3除数、商与余数之和为 ，则被除数是多少？213【 被除数 除数 商 余数 被除数 除数+17+13=2113，所以被除数 除数=2083，由于被除数是除数的 17 倍还多 13，则由“和倍问题”可得：除数 =（2083-13）（17+1）=115，所以被除数=2083-115=1968【 用一个自然数去除另一个自然数，商为 40，余数是 16.被除数、除数、商、余数的和是 933，求这 2 个自然数各是多少？【 本题为带余除法定义式的基本题型。根据 题意设两个自然数分别为 x,y，可以得到,解方程组得 ，即 这两个自然数分 别是 856，21.401693xy85621xy【例 3】 (20

14、00 年“祖冲之杯”小学数学邀请赛试题)三个不同的自然数的和为 2001，它们分别除以19,23,31 所得的商相同，所得的余数也相同，这三个数是_，_，_。【 设所得的商为 ，除数 为 ， ，由 ，可ab(19)(23)(1)20aba73201ab9b求得 ， 所以， 这三个数分别是 ， ， 。2709536847【 (2004 年福州市“迎春杯”小学数学竞赛试题) 一个自然数，除以 11 时所得到的商和余数是相等的，除以 9 时所得到的商是余数的 3 倍，这个自然数是_【 设这个自然数除以 11 余 ，除以 9 余 ，则有 ，即 ，a(01)b(09)193ab7ab只有 ， ，所以 这

15、个自然数为 。7a3b8472【例 4】 (1997 年我爱数学少年数学夏令营试题)有 48 本书分给两组小朋友，已知第二组比第一组多 5人如果把书全部分给第一组，那么每人 4 本，有剩余；每人 5 本，书不够如果把书全分给第二组，那么每人 3 本，有剩余；每人 4 本，书不够问：第二组有多少人? 【 由 ， 知，一组是 10 或 11 人同理可知 ， 知，二 组是481259.6483164213、14 或 15 人，因 为二组比一组多 5 人，所以二组只能是 15 人，一组 10 人【 一个两位数除以 13 的商是 6，除以 11 所得的余数是 6，求这个两位数【 因为一个两位数除以 13

16、 的商是 6，所以 这个两位数一定大于 ，并且小于 ；137813(6)91又因为这个两位数除以 11 余 6，而 78 除以 11 余 1，这个两位数为 5【模块二：三大余数定理的应用】【例 5】 有一个大于 1 的整数，除 所得的余数相同，求这个数.45,910【 这个题没有告诉我们， 这三个数除以这个数的余数分别是多少，但是由于所得的余数相同，根据同余定理，我们可以得到：这个数一定能整除 这三个数中的任意两数的差，也就是 说它是任意两数差的公约数 ， ， ， 的约数有 ，所以这个数可能为104569451(6,4)11,274。2,74【 有一个整数，除 39,51,147 所得的余数都

17、是 3，求这个数.【 (法 1) ， ， ，12 的约数是 ，因 为余数为 3 要小于除3961473(6,14)21,2346,数，这个数是 ；,2(法 2)由于所得的余数相同，得到这个数一定能整除这三个数中的任意两数的差，也就是说它是任意两数差的公约数 ， ， ，所以这个数是 51394739108(2,)14,612【 在小于 1000 的自然数中，分别除以 18 及 33 所得余数相同的数有多少个?(余数可以为 0) 【 我们知道 18，33 的最小公倍数 为18 ，33=198，所以每 198 个数一次 1198 之间只有 1，2，3，17，198(余 O)这 18 个数除以 18

18、及 33 所得的余数相同，而 999198=59，所以共有 518+9=99 个这样的数【 (2008 年仁华考题)一个三位数除以 17 和 19 都有余数，并且除以 17 后所得的商与余数的和等于它除以 19 后所得到的商与余数的和那么这样的三位数中最大数是多少，最小数是多少？【 设这个三位数为 ，它除以 17 和 19 的商分别为 和 ，余数分别为 和 ，则s abmn179sambn根据题意可知 ，所以 ，即 ，得 所以 是 9 的smsn168ab9aa倍数， 是 8 的倍数此时，由 知 bab9由于 为三位数，最小为 100，最大为 999，所以 ，而 ，s 107a16m所以 ，

19、，得到 ，而 是 9 的倍数，所以 最179am1076m58aa小为 9，最大为 54当 时， ，而 ，所以 ，故此时 最大为 ；5469na8n12s1754230当 时， ，由于 ，所以此时 最小为 9a1ms9所以这样的三位数中最大的是 930，最小的是 154【例 6】 两位自然数 与 除以 7 都余 1，并且 ，求 ababa【 能被 7 整除，即 能被 7 整除所以只能有 ，那么ab(0)9ab（ （ ） 7ab可能为 92 和 81，验算可得当 时， 满足题目要求，2 ba9268b【 学校新买来 118 个乒乓球，67 个乒乓球拍和 33 个乒乓球网，如果将这三种物品平分给每

20、个班级，那么这三种物品剩下的数量相同请问学校共有多少个班？【 所求班级数是除以 余数相同的数那么可知该数应该为 和18,673 1867534的公约数，所求答案为 17【 (2000 年全国小学数学奥林匹克试题)在除 13511，13903 及 14589 时能剩下相同余数的最大整数是_【 因为 , ，39215390681390458由于 13511，13903，14589 要被同一个数除时，余数相同，那么，它们两两之差必能被同一个数整除 ，所以所求的最大整数是 9898)6,32(【例 7】 (2003 年南京市少年数学智力冬令营试题) 与 的和除以 7 的余数是_2032【 找规律用 7

21、 除 2， ， ， ， ， ，的余数分别是 2，4，1，2，4，1，2，4，1，,2 的个数是345263 的倍数时，用 7 除的余数为 1；2 的个数是 3 的倍数多 1 时，用 7 除的余数为 2；2 的个数是 3 的倍数多 2 时，用 7 除的余数为 4因为 ，所以 除以 7 余 4又两个数的 积除以 720672203的余数，与两个数分别除以 7 所得余数的积相同而 2003 除以 7 余 1，所以 除以 7 余 1故203与 的和除以 7 的余数是 2032 15【 (2004 年南京市少年数学智力冬令营试题)在 1995，1998，2000，2001，2003 中，若其中几个数的和

22、被 9 除余 7，则将这几个数归为一组这样的数组共有_组【 1995，1998，2000，2001，2003 除以 9 的余数依次是 6，0，2，3，5因为 ， ，250253602579所以这样的数组共有下面 4 个： ， ，,18， 19,3,0 ,8【例 8】 (2005 年全国小学数学奥林匹克试题)有一个整数，用它去除 70，110，160 所得到的 3 个余数之和是 50，那么这个整数是_【 ， ，除数应当是 290 的大于 17 小于 70 的约数，只可能(7016)5029316.2是 29 和 58， ， ，所以除数不是 5881.50， ， ， ，所以除数是29.9.1550

23、12329【 (2002 年全国小学数学奥林匹克试题)用自然数 n 去除 63，91，129 得到的三个余数之和为25，那么 n=_【 n 能整除 因 为 ，所以 n 是 258 大于 8 的约数显然，n 不258196338.1能大于 63符合条件的只有 43【 号码分别为 101,126,173,193 的 4 个运动员进行乒乓球比赛,规定每两人比赛的盘数是他们号码的和被 3 除所得的余数.那么打球盘数最多的运动员打了多少盘? 【 本题可以体现出加法余数定理的巧用。 计算 101，126，173，193 除以 3 的余数分别为 2，0，2，1。那么任意两名运动员的比赛盘数只需要用 2，0，

24、2，1 两两相加除以 3 即可。显然 126 运动员打 5盘是最多的。【例 9】 (2002 年小学生数学报数学邀请赛试题)六名小学生分别带着 14 元、17 元、18 元、21 元、26 元、37 元钱，一起到新华书店购买成语大词典 一看定价才发现有 5 个人带的钱不够，但是其中甲、乙、丙 3 人的钱凑在一起恰好可买 2 本，丁、戊 2 人的钱凑在一起恰好可买 1本这种成语大词典的定价是_元【 六名小学生共带钱 133 元 133 除以 3 余 1，因为甲、乙、丙、丁、戊的钱恰好能买 3 本，所以他们五人带的钱数是 3 的倍数，另一人带的钱除以 3 余 1易知， 这个钱数只能是 37 元，所

25、以每本成语大词典的定价是 (元) (147826)2【 (2000 年全国小学数学奥林匹克试题)商店里有六箱货物，分别重 15，16，18，19，20，31 千克，两个顾客买走了其中的五箱已知一个顾客买的货物重量是另一个顾客的 2 倍，那么商店剩下的一箱货物重量是_千克【 两个顾客买的货物重量是 的倍数3，剩下的一箱货物重量除以 3 应当余 2，只能(15681920)(1293.2是 20 千克【例 10】 求 的余数2461350471【 因为 ， ， ，根据同余定理(三)， 2.8352.36047159.8的余数等于 的余数，而 ，8312，所以 的余数为 51927.5461【 (华

26、罗庚金杯赛模拟试题)求 除以 17 的余数782931【 先求出乘积再求余数， 计算量较大可先分别计算出各因数除以 17 的余数，再求余数之积除以 17 的余数 除以 17 的余数分别为 2，7 和 11， 478,296351(271)9.1【 求 的最后两位数1973【 即考虑 除以 100 的余数由于 ，由于 除以 25 余 2，所以 除以 25 余 8，1042532793除以 25 余 24，那么 除以 25 余 1；又因为 除以 4 余 1，则 除以 4 余 1；即 能被 4 10 203 020和 25 整除，而 4 与 25 互质，所以 能被 100 整除，即 除以 100 余

27、 1，由于202，所以 除以 100 的余数即等于 除以 100 的余数，而 除以 100 余97217197 173637929， 除以 100 余 43， ，所以 除以 100 的余数等于 除以 100 的536253()24余数，而 除以 100 余 63，所以 除以 100 余 63，即 的最后两位数为 63946197197【 除以 13 所得余数是_. “20个【 我们发现 222222 整除 13，20006 余 2，所以答案为 2213 余 9。【 求 除以 7 的余数89143【 法一：由于 (143 被 7 除余 3)，mod所以 ( 被 7 除所得余数与 被 7 除所得余

28、数相等)8914389143893而 ， （729 除以 7 的余数为 1），672od所以 896651433mod个故 除以 7 的余数为 5.8914法二：计算 被 7 除所得的余数可以用找规律的方法，规律如下表：8931323453673mod61于是余数以 6 为周期变化所以 895mod7【 （2007 年实验中学考题） 除以 7 的余数是多少？2221301【 由于 ，而 1001 是 7 的倍数，22 345130012356所以这个乘积也是 7 的倍数，故 除以 7 的余数是 0；2221【 被 除所得的余数是多少？3013【 31 被 13 除所得的余数为 5，当 n 取

29、1，2，3， 时 被 13 除所得余数分别是 5n5，12，8，1，5，12，8，1 以 4 为周期循环出现，所以 被 13 除的余数与 被 13 除的余数相同， 3025余 12，则 除以 13 的余数 为 12；3030 被 13 除所得的余数是 4，当 n 取 1，2，3， 时， 被 13 除所得的余数分别是 4n4，3，12，9，10，1，4，3，12，9，10， 以 6 为周期循环出现，所以 被 13 除所得的余数等于 314被 13 除所得的余数，即 4，故 除以 13 的余数为 4；1 310所以 被 13 除所得的余数是 30123【 (2008 年奥数网杯)已知 ，问： 除以

30、 13 所得的余数是多少？208a个 a【 2008 除以 13 余 6，10000 除以 13 余 3，注意到 ；20801208；2082081；208 根据这样的递推规律求出余数的变化规律：20082008 除以 13 余 ，200820082008 除以 13 余 ，即63113690200820082008 是 13 的倍数而 除以 3 余 1，所以 除以 13 的余数与 除以 13 的余数相同， 为 6.208208a个 208【 除以 41 的余数是多少？1967个【 找规律： ， ， ， ，47 4136 74139 74128，所以 77777 是 41 的倍数，而 ，所以

31、可以分0 65 1967个成 399 段 77777 和 1 个 7 组成，那么它除以 41 的余数为 7【 除以 10 所得的余数为多少？1234205 【 求结果除以 10 的余数即求其个位数字从 1 到 2005 这 2005 个数的个位数字是 10 个一循环的，而对一个数的幂方的个位数，我们知道它总是 4 个一循环 的，因此把所有加数的个位数按每 20 个(20 是 4 和 10 的最小公倍数) 一组， 则不同组中对应的个位数字应该是一样的首先计算 的个位数字，123420 为 的个位数字，为 4，76569163567490由于 2005 个加数共可分成 100 组另 5 个数， 100 组的个位数字和是 的个位数即 0，10另外 5 个数为 、 、 、 、 ，它们和的个位数字是20120203204205的个位数 3，所以原式的个位数字是 3，即除以 10 的余数是 31476【例 11】 求所有的质数 P，使得 与 也是质数241p26【 如果 ，则 ， 都是质数，所以 5 符合题意如果 P 不等于 5，那么 P 除5p205以 5 的余数为 1、2、3 或者 4， 除以 5 的余数即等于 、 、 或者 除以 5 的余数，即2p212324