小学奥数—同余问题.doc

《小学奥数—同余问题.doc》由会员分享，可在线阅读，更多相关《小学奥数—同余问题.doc（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、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，16 除以 5 的余数

3、分别是 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。当余数的和比除数大时，所求的余数等于余数之积再除以 c 的余数。例如：23，19

4、 除以 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，那么上面这个算式一定是错的。上述检验方法恰好用到的就是我们前面所讲的余数的加法定理，即如果这个等式是正确的，那么左边几个加数除以 9 的余数的和再除以 9 的

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

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

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

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

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

11、讲：【模块一：带余除法的定义和性质】【例 1】 (第五届小学数学报竞赛决赛)用某自然数 去除 ，得到商是 46，余数是 ，求 和 a192rar【 解析解析 】 因为 是 的 倍还多 ,得到 ，得 ，所以 ，192a46r192463.463143r【 巩固巩固 】 (清华附中小升初分班考试) 甲、乙两数的和是 ，甲数除以乙数商 余 ，求甲、乙两数082【 解析解析 】 (法 1)因为 甲 乙 ，所以 甲 乙 乙 乙 乙 ；1321321308则乙 ，甲 乙 108)810(法 2)将余数先去掉变成整除性问题，利用倍数关系来做：从 中减掉 以后， 就应当082156是乙数的 倍，所以得到乙数

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

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

14、 3】 (2000 年“祖冲之杯”小学数学邀请赛试题)三个不同的自然数的和为 2001，它们分别除以19,23,31 所得的商相同，所得的余数也相同，这三个数是_，_，_。【 解析解析 】 设所得的商为 ，除数为 ， ，由 ，ab(19)(23)(1)20aba73201ab9b|可求得 ， 所以，这三个数分别是 ， ， 。27a10b19523ab631ab847ab【 巩固巩固 】 (2004 年福州市“迎春杯”小学数学竞赛试题) 一个自然数，除以 11 时所得到的商和余数是相等的，除以 9 时所得到的商是余数的 3 倍，这个自然数是_【 解析解析 】 设这个自然数除以 11 余 ，除以

15、9 余 ，则有 ，即a(01)b(09)193ab，只有 ， ，所以这个自然数为 。37ab7b84712【例 4】 (1997 年我爱数学少年数学夏令营试题)有 48 本书分给两组小朋友，已知第二组比第一组多 5人如果把书全部分给第一组，那么每人 4 本，有剩余；每人 5 本，书不够如果把书全分给第二组，那么每人 3 本，有剩余；每人 4 本，书不够问：第二组有多少人? 【 解析解析 】 由 ， 知，一组是 10 或 11 人同理可知 ， 知，二组48124859.6483164812是 13、14 或 15 人，因为二组比一组多 5 人，所以二组只能是 15 人，一组 10 人【 巩固巩固

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

17、有 ，所以这个104569451(6,4)11,274数可能为 。2,7【 巩固巩固 】 有一个整数，除 39,51,147 所得的余数都是 3，求这个数.【解析】 (法 1) ， ， ，12 的约数是 ，因为余数为 3 要小3961473(6,14)21,2346,于除数，这个数是 ；,2(法 2)由于所得的余数相同，得到这个数一定能整除这三个数中的任意两数的差，也就是说它是任意两数差的公约数 ， ， ，所以这个数是 51391473908(12,)4,612|【 巩固巩固 】 在小于 1000 的自然数中，分别除以 18 及 33 所得余数相同的数有多少个?(余数可以为 0) 【解析】 我

18、们知道 18，33 的最小公倍数为18，33=198，所以每 198 个数一次 1198 之间只有 1，2，3，17，198(余 O)这 18 个数除以 18 及 33 所得的余数相同，而 999198=59，所以共有 518+9=99 个这样的数【 巩固巩固 】 (2008 年仁华考题)一个三位数除以 17 和 19 都有余数，并且除以 17 后所得的商与余数的和等于它除以 19 后所得到的商与余数的和那么这样的三位数中最大数是多少，最小数是多少？【解析】 设这个三位数为 ，它除以 17 和 19 的商分别为 和 ，余数分别为 和 ，则s abmn179sambn根据题意可知 ，所以 ，即

19、，得 所以 是 9smsn168ab9aa的倍数， 是 8 的倍数此时，由 知 bab9由于 为三位数，最小为 100，最大为 999，所以 ，而 ，s 107am16所以 ， ，得到 ，而 是 9 的倍数，所以179am1076m58a最小为 9，最大为 54当 时， ，而 ，所以 ，故此时 最大为 ；546na8n12s1754230当 时， ，由于 ，所以此时 最小为 9a19m1ms9所以这样的三位数中最大的是 930，最小的是 154【例 6】 两位自然数 与 除以 7 都余 1，并且 ，求 ababa【解析】 能被 7 整除，即 能被 7 整除所以只能有 ，那么ab(0)9ab（

20、（ ） 7ab可能为 92 和 81，验算可得当 时， 满足题目要求，2 ba9268b【 巩固巩固 】 学校新买来 118 个乒乓球，67 个乒乓球拍和 33 个乒乓球网，如果将这三种物品平分给每个班级，那么这三种物品剩下的数量相同请问学校共有多少个班？【解析】 所求班级数是除以 余数相同的数那么可知该数应该为 和18,673 1867534的公约数，所求答案为 17【 巩固巩固 】 (2000 年全国小学数学奥林匹克试题)在除 13511，13903 及 14589 时能剩下相同余数的最大整数是_【解析】 因为 , ，39215390681390458|由于 13511，13903，145

21、89 要被同一个数除时，余数相同，那么，它们两两之差必能被同一个数整除 ，所以所求的最大整数是 9898)6,32(【例 7】 (2003 年南京市少年数学智力冬令营试题) 与 的和除以 7 的余数是_2032【解析】 找规律用 7 除 2， ， ， ， ， ，的余数分别是 2，4，1，2，4，1，2，4，1，,234256的个数是 3 的倍数时，用 7 除的余数为 1；2 的个数是 3 的倍数多 1 时，用 7 除的余数为 2；2的个数是 3 的倍数多 2 时，用 7 除的余数为 4因为 ，所以 除以 7 余 4又两20672203个数的积除以 7 的余数，与两个数分别除以 7 所得余数的积

22、相同而 2003 除以 7 余 1，所以除以 7 余 1故 与 的和除以 7 的余数是 202032 15【 巩固巩固 】 (2004 年南京市少年数学智力冬令营试题)在 1995，1998，2000，2001，2003 中，若其中几个数的和被 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

23、所得到的 3 个余数之和是 50，那么这个整数是_【解析】 ， ，除数应当是 290 的大于 17 小于 70 的约数，只可能(7016)5029316.2是 29 和 58， ， ，所以除数不是 5881.50， ， ， ，所以除数是29.9.155012329【 巩固巩固 】 (2002 年全国小学数学奥林匹克试题)用自然数 n 去除 63，91，129 得到的三个余数之和为25，那么 n=_【解析】 n 能整除 因为 ，所以 n 是 258 大于 8 的约数显然，n258196338.1不能大于 63符合条件的只有 43【 巩固巩固 】 号码分别为 101,126,173,193 的 4

24、 个运动员进行乒乓球比赛,规定每两人比赛的盘数是他们号码的和被 3 除所得的余数.那么打球盘数最多的运动员打了多少盘? 【解析】 本题可以体现出加法余数定理的巧用。计算 101，126，173，193 除以 3 的余数分别为|2，0，2，1。那么任意两名运动员的比赛盘数只需要用 2，0，2，1 两两相加除以 3 即可。显然126 运动员打 5 盘是最多的。【例 9】 (2002 年小学生数学报数学邀请赛试题)六名小学生分别带着 14 元、17 元、18 元、21 元、26 元、37 元钱，一起到新华书店购买成语大词典 一看定价才发现有 5 个人带的钱不够，但是其中甲、乙、丙 3 人的钱凑在一起

25、恰好可买 2 本，丁、戊 2 人的钱凑在一起恰好可买 1本这种成语大词典的定价是_元【解析】 六名小学生共带钱 133 元133 除以 3 余 1，因为甲、乙、丙、丁、戊的钱恰好能买 3 本，所以他们五人带的钱数是 3 的倍数，另一人带的钱除以 3 余 1易知，这个钱数只能是 37 元，所以每本成语大词典的定价是 (元) (47826)2【 巩固巩固 】 (2000 年全国小学数学奥林匹克试题)商店里有六箱货物，分别重 15，16，18，19，20，31 千克，两个顾客买走了其中的五箱已知一个顾客买的货物重量是另一个顾客的 2 倍，那么商店剩下的一箱货物重量是_千克【解析】 两个顾客买的货物重

26、量是 的倍数3，剩下的一箱货物重量除以 3 应当余 2，只能(15681920)(1293.2是 20 千克【例 10】 求 的余数2461350471【解析】 因为 ， ， ，根据同余定理(三)， 2.83512.36047159.8的余数等于 的余数，而 ，8312，所以 的余数为 51927.546【 巩固巩固 】 (华罗庚金杯赛模拟试题)求 除以 17 的余数7829351【解析】 先求出乘积再求余数，计算量较大可先分别计算出各因数除以 17 的余数，再求余数之积除以 17 的余数 除以 17 的余数分别为 2，7 和 11， 478,296351(271)9.1【 巩固巩固 】 求

27、的最后两位数1973【解析】 即考虑 除以 100 的余数由于 ，由于 除以 25 余 2，所以 除以 25 余 8，1042532793除以 25 余 24，那么 除以 25 余 1；又因为 除以 4 余 1，则 除以 4 余 1；即 能被10 203 0204 和 25 整除，而 4 与 25 互质，所以 能被 100 整除，即 除以 100 余 1，由于2032，所以 除以 100 的余数即等于 除以 100 的余数，而 除以 10097217197 1736379|余 29， 除以 100 余 43， ，所以 除以 100 的余数等于 除以5324176253()1732943100

28、的余数，而 除以 100 余 63，所以 除以 100 余 63，即 的最后两位99 17数为 63【 巩固巩固 】 除以 13 所得余数是_. “20个【解析】 我们发现 222222 整除 13，20006 余 2，所以答案为 2213 余 9。【 巩固巩固 】 求 除以 7 的余数89143【解析】 法一：由于 (143 被 7 除余 3)，mod所以 ( 被 7 除所得余数与 被 7 除所得余数相等)8914389143893而 ， （729 除以 7 的余数为 1） ，672od所以 896651433mod个故 除以 7 的余数为 5.8914法二：计算 被 7 除所得的余数可以用

29、找规律的方法，规律如下表：8931323453673mod61于是余数以 6 为周期变化所以 895mod7【 巩固巩固 】 （2007 年实验中学考题） 除以 7 的余数是多少？2221301【解析】 由于 ，而 1001 是 7 的倍22 345130012356数，所以这个乘积也是 7 的倍数，故 除以 7 的余数是 0；221【 巩固巩固 】 被 除所得的余数是多少？3013【解析】 31 被 13 除所得的余数为 5，当 n 取 1，2，3， 时 被 13 除所得余数分别是 5n5，12，8，1，5，12，8，1 以 4 为周期循环出现，所以 被 13 除的余数与 被 13 除的余数

30、 3025相同，余 12，则 除以 13 的余数为 12；3030 被 13 除所得的余数是 4，当 n 取 1，2，3， 时， 被 13 除所得的余数分别是 4n|4，3，12，9，10，1，4，3，12，9，10， 以 6 为周期循环出现，所以 被 13 除所得的余 314数等于 被 13 除所得的余数，即 4，故 除以 13 的余数为 4；310所以 被 13 除所得的余数是 3012【 巩固巩固 】 (2008 年奥数网杯)已知 ，问： 除以 13 所得的余数是多少？208a个 a【解析】 2008 除以 13 余 6，10000 除以 13 余 3，注意到 ；20801208；208

31、2081；208 根据这样的递推规律求出余数的变化规律：20082008 除以 13 余 ，200820082008 除以 13 余 ，即63113690200820082008 是 13 的倍数而 除以 3 余 1，所以 除以 13 的余数与 除以 13 的余数相同，为 6.208208a个 208【 巩固巩固 】 除以 41 的余数是多少？1967个【解析】 找规律： ， ， ， ，47 4136 74139 74128，所以 77777 是 41 的倍数，而 ，所以 可以0 65 1967个分成 399 段 77777 和 1 个 7 组成，那么它除以 41 的余数为 7【 巩固巩固 】

32、 除以 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