小学奥数—同余问题

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

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

3、余数之和再除以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，所以23X16除以5的余数等于3X仁3。C的余数。当余数的和比除数大时，所求的余数等于余数之积再除以例如：23,19除以5的余数分别是3和4，所以23X19除以5的余数等于3X4除以5的余数，即2.3.同余定理若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：aMb(modm),左边的式子

4、叫做同余式。同余式读作：a同余于b，模m。由同余的性质，我们可以得到一个非常重要的推论：若两个数a,b除以同一个数m得到的余数相同，则a,b的差一定能被m整除用式子表示为：如果有aMb(modm)，那么一定有a-b=mk,k是整数，即m|(a-b)三、弃九法原理：在公元前9世纪，有个印度数学家名叫花拉子米，写有一本花拉子米算术，他们在计算时通常是在一个铺有沙子的土板上进行，由于害怕以前的计算结果丢失而经常检验加法运算是否正确，他们的检验方式是这样进行的：例如：检验算式12341898189226789671789028899231234除以9的余数为11898除以9的余数为818922除以9的

5、余数为4678967除以9的余数为7178902除以9的余数为0这些余数的和除以9的余数为2而等式右边和除以9的余数为3,那么上面这个算式一定是错的。上述检验方法恰好用到的就是我们前面所讲的余数的加法定理，即如果这个等式是正确的，那么左边几个加数除以9的余数的和再除以9的余数一定与等式右边和除以9的余数相同。而我们在求一个自然数除以9所得的余数时，常常不用去列除法竖式进行计算，只要计算这个自然数的各个位数字之和除以9的余数就可以了，在算的时候往往就是一个9一个9的找并且划去，所以这种方法被称作“弃九法”所以我们总结出弃九发原理：任何一个整数模9同余于它的各数位上数字之和。以后我们求一个整数被9

6、除的余数，只要先计算这个整数各数位上数字之和，再求这个和被9除的余数即可°利用十进制的这个特性，不仅可以检验几个数相加，对于检验相乘、相除和乘方的结果对不对同样适用注意：弃九法只能知道原题一定是错的或有可能正确，但不能保证一定正确。例如：检验算式9+9=9时，等式两边的除以9的余数都是0，但是显然算式是错误的但是反过来，如果一个算式一定是正确的，那么它的等式2两端一定满足弃九法的规律。这个思想往往可以帮助我们解决一些较复杂的算式迷问题°四、中国剩余定理：1 .中国古代趣题：中国数学名着孙子算经里有这样的问题：“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二

7、，问物几何”答曰：“二十三。”此类问题我们可以称为“物不知其数”类型，又被称为“韩信点兵”。韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人。刘邦茫然而不知其数。我们先考虑下列的问题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积），然后再加3，得9948（人）。孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之后，以这个考

8、证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理（ChineseRemainderTheorem）在近代抽象代数学中占有一席非常重要的地位。2 .核心思想和方法：对于这一类问题，我们有一套看似繁琐但是一旦掌握便可一通百通的方法，下面我们就以孙子算经中的问题为例，分析此方法：今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何题目中我们可以知道，一个自然数分别除以3，5，7后，得到三个余数分别为2，3，2.那么我们首先构造一个数字，使得这个数字除以3余1，并且还是5和7的公倍数。先由5735，即5和7的最小公倍数出

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

10、上面条件最小的三位自然数”，我们只要对最小的23加上3,5,7即可，即23+105=128。例题精讲：【模块一：带余除法的定义和性质】【例1】（第五届小学数学报竞赛决赛）用某自然数a去除1992,得到商是46,余数是r，求a和r.【解析】因为1992是a的46倍还多r得至ij1992464314得1992464314，所以a43,r14.巩固】（清华附中小升初分班考试）甲、乙两数的和是1088，甲数除以乙数商11余32，求甲、乙两数解析】（法1）因为甲乙11 32，所以甲乙乙11 32乙乙 12 32 1088 ；则乙（108832）1288，甲1088乙1000.（法2）将余数先去掉变成整除

11、性问题，利用倍数关系来做：从1088中减掉32以后,1056就应当1088 88 1000 .是乙数的（111）倍，所以得到乙数10561288,甲数巩固】个两位数除310，余数是37，求这样的两位数。解析】本题为余数问题的基础题型，需要学生明白一个重要知识点，就是把余数问题一即“不整除问题”转化为整除问题。方法为用被除数减去余数，即得到一个除数的倍数；或者是用被除数加上一个“除数与余数的差”，也可以得到一个除数的倍数。本题中31037=273，说明273是所求余数的倍数，而273=3X7X13，所求的两位数约数还要满足比37大，符合条件的有39，91.例2（2003年全国小学数学奥林匹克试题

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

13、16 933y21例3（2000年“祖冲之杯”小学数学邀请赛试题）三个不同的自然数的和为2001,它们分别除以19,23,31所得的商相同，所得的余数也相同，这三个数是,。【解析】设所得的商为a，除数为b.（19ab）（23ab）（31ab）2001,73a3b2001,由b19,可求得a27,b10,所以，这三个数分别是19ab523,23ab631,31ab847。巩固】（2004年福州市“迎春杯”小学数学竞赛试题）一个自然数，除以11时所得到的商和余数是相等的，除以9时所得到的商是余数的3倍,这个自然数是.【解析】设这个自然数除以W余a（0a11），除以9余b（0b9），则有11aa93

14、bb，即3a7b,只有a7，b3，所以这个自然数为12784。例4】（1997年我爱数学少年数学夏令营试题）有48本书分给两组小朋友，已知第二组比第一组多5人-如果把书全部分给第一组，那么每人4本，有剩余；每人5本，书不够-如果把书全分给第二组，那么每人3本，有剩余；每人4本，书不够,问：第二组有多少人？解析】由48412，4859.6知，一组是10或11人同理可知48316，48412知，二组是13、14或15人，因为二组比一组多5人，所以二组只能是15人，一组10人-巩固】一个两位数除以13的商是6，除以11所得的余数是6，求这个两位数-解析】因为一个两位数除以13的商是6，所以这个两位数

15、一定大于13678，并且小于13（61）91；又因为这个两位数除以11余6，而78除以11余1，这个两位数为78583模块二：三大余数定理的应用】例5】有一个大于1的整数，除45,59,101所得的余数相同，求这个数.解析】这个题没有告诉我们，这三个数除以这个数的余数分别是多少，但是由于所得的余数相同，根据同余定理，我们可以得到：这个数一定能整除这三个数中的任意两数的差，也就是说它是任意两数差的公约数-1014556，594514，（56,14）14，14的约数有1,2,7,14，所以这个数可能为2,7,14。巩固】有一个整数，除39,51,147所得的余数都是3，求这个数.解析】（法1）39

16、3361473144，（36,144）12，12的约数是1,2,3,4,6,12，因为余数为3要小于除数，这个数是4,6,12；（法2）由于所得的余数相同，得到这个数一定能整除这三个数中的任意两数的差，也就是说它是任意两数差的公约数513912，14739108，（12,108）12，所以这个数是4,6,12巩固】在小于1000的自然数中，分别除以18及33所得余数相同的数有多少个？（余数可以为0）解析】我们知道18，33的最小公倍数为18，33=198，所以每198个数一次1198之间只有1,2,3，17,198（余0）这18个数除以18及33所得的余数相同，而999+198=59，所以共有

17、508+9=99个这样的数.巩固】（2008年仁华考题）一个三位数除以17和19都有余数，并且除以17后所得的商与余数的和等于它除以19后所得到的商与余数的和那么这样的三位数中最大数是多少，最小数是多少【解析】设这个三位数为s，它除以17和19的商分别为a和b，余数分别为m和n,则s17am19bn.根据题意可知ambn，所以samsbn，即16al8b，得8a9b.所以a是9的倍数，b是8的倍数.此时，由ambn知nmabaa-a.99由于s为三位数，最小为100,最大为999,所以10017am999,而1m16,所以17al17am999,10017am17al6，得到5a58,而a是9

18、的倍数，所以a最小为9,最大为54.1当a54时，nma6，而n18，所以m12，故此时s最大为175412930；91当a9时，nma1，由于m1，所以此时s最小为1791154.9所以这样的三位数中最大的是930，最小的是154.【例6】两位自然数ab与ba除以7都余1，并且ab，求abba.【解析】abba能被7整除，即（10ab）（10ba）9（ab）能被7整除.所以只能有ab7，那么ab可能为92和81，验算可得当ab92时，ba29满足题目要求，abba92292668【巩固】学校新买来118个乒乓球，67个乒乓球拍和33个乒乓球网，如果将这三种物品平分给每个班级，那么这三种物品剩

19、下的数量相同.请问学校共有多少个班【解析】所求班级数是除以W8,67,33余数相同的数.那么可知该数应该为1186751和673334的公约数，所求答案为17.【巩固】（2000年全国小学数学奥林匹克试题）在除13511,13903及14589时能剩下相同余数的最大整数是.【解析】因为1390313511392,1458913903686,由于13511,13903,14589要被同一个数除时，余数相同，那么，它们两两之差必能被同一个数整除.（392,686）98，所以所求的最大整数是98.例7（2003年南京市少年数学智力冬令营试题）22。3与20032的和除以7的余数是.【解析】找规律.用

20、7除2,22,23,24,25,26,的余数分别是2,4,1,2,4,1,2,4,1，,2的个数是3的倍数时，用7除的余数为1;2的个数是3的倍数多1时，用7除的余数为2;2的个数是3的倍数多2时，用7除的余数为4因为22003236672,所以22。3除以7余4又两个数的积除以7的余数，与两个数分别除以7所得余数的积相同而2003除以7余1，所以20032除以7余1故2?。3与20032的和除以7的余数是415-巩固】（2004年南京市少年数学智力冬令营试题）在1995，1998，2000，2001，2003中，若其中几个数的和被9除余7，则将这几个数归为一组这样的数组共有组-解析】1995

21、7998，2000，2001，2003除以9的余数依次是6，0，2，3，5因为252507，25360253679，所以这样的数组共有下面4个：2000,2003，1998,2000,2003，2000,2003,2001,1995，1998,2000,2003,2001,1995例8（2005年全国小学数学奥林匹克试题）有一个整数，用它去除70，110，160所得到的3个余数之和是50，那么这个整数是解析】（70110160）50290，503162，除数应当是290的大于17小于70的约数，只可能是29和58，11058152，5250，所以除数不是587029212，11029323，1

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

23、两两相加除以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元，所以每本成语大词典的定价是（1417182126）332（元）巩固】（2000年全国小学数学奥林

24、匹克试题）商店里有六箱货物，分别重15，16，18，19，20，31千克，两个顾客买走了其中的五箱已知一个顾客买的货物重量是另一个顾客的2倍，那么商店剩下的一箱货物重量是千克解析】两个顾客买的货物重量是3的倍数-（151618192031）（12）119339.2，剩下的一箱货物重量除以3应当余2，只能是20千克例10】求2461135604711的余数解析】因为246111223.8，1351112.3，604711549.8，根据同余定理，2461135604711的余数等于83811的余数，而838192，1921117.5，所以2461135604711的余数为5巩固】（华罗庚金杯赛模

25、拟试题）求478296351除以17的余数-解析】先求出乘积再求余数，计算量较大-可先分别计算出各因数除以17的余数，再求余数之积除以17的余数478,296,351除以17的余数分别为2，7和11，（2711）1791巩固】求3侬7的最后两位数解析】即考虑3项7除以100的余数由于100425，由于3327除以25余2，所以39除以25余8，10202202。31。除以25余24，那么32。除以25余1；又因为3?除以4余1，则3?。除以4余1；即3?。1能被4和25整除，而4与25互质，所以3201能被100整除，即32。除以100余1，由于1997209917所以31997除以100的余

26、数即等于317除以100的余数，而36729除以100余29，35243除以100余43，3。产35，所以3"除以100的余数等于292943除以100的余数，而29294336163除以100余63，所以3.除以1。余63，即3侬7的最后两位数为63-巩固】2222除以13所得余数是.2000个"2"【解析】我们发现222222整除13,2000北余2，所以答案为22+13余9。【巩固】求14389除以7的余数.【解析】法一：由于1433mod7（143被7除余3）,89898989所以1433mod7（143被7除所得余数与3被7除所得余数相等）而36729，

27、7291mod7（729除以7的余数为1），所以389363二3635355mod7.1）个“故14389除以7的余数为5.法二：计算389被7除所得的余数可以用找规律的方法，规律如下表：于是余数以6为周期变化.所以389355mod7.【巩固】（2007年实验中学考题）122232川200122002除以7的余数是多少【解析】由于122232HI200122002220022?34005100120031335，而1001是7的倍数，所以这个乘积也是7的倍数，故122232川200#20022除以7的余数是0；【巩固】3/。3（F被13除所得的余数是多少【解析】31被13除所得的余数为5,当

28、n取1,2,3,时5n被13除所得余数分别是5,12,8,1,5,12,8,1以4为周期循环出现，所以53。被13除的余数与52被13除的余数相同，余12,则3皆。除以13的余数为12;30被13除所得的余数是4,当n取1,2,3,时，4n被13除所得的余数分别是4,3,12,9,10,1,4,3,12,9,10,以6为周期循环出现，所以被13除所得的余数等于邛被13除所得的余数，即4，故3031除以13的余数为4;所以31303031被13除所得的余数是124133.【巩固】（2008年奥数网杯）已知a2008200,8卅2008，问：a除以13所得的余数是多少2008个2008【解析】20

29、08除以13余6,10000除以13余3，注意到200820082008100002008;20082008200820082008100002008；2008200820082008200820082008100002008；根据这样的递推规律求出余数的变化规律：而2008除以3余1，所以a20082008卅2008除以13的余数与2008除以13的余数相同，为6.2008个2008【巩固】77777除以41的余数是多少1996'个7【解析】找规律：7417，774136，77741口39，77774128,77777410,，所以77777是41的倍数，而19965399川1，所以

30、口八嘉口可以分成399段77777和1个7组成，那么它除以41的余数为7.【巩固】223344卅卅20052。5除以10所得的余数为多少【解析】求结果除以1。的余数即求其个位数字.从1到2005这2005个数的个位数字是10个一循环的，而对一个数的幕方的个位数，我们知道它总是4个一循环的，因此把所有加数的个位数按每20个（20是4和10的最小公倍数）一组，则不同组中对应的个位数字应该是一样的.首先计算皆22334,卅川202。的个位数字，为1476563690163656749094的个位数字，为4,由于2005个加数共可分成100组另5个数，100组的个位数字和是4100400的个位数即0,

31、另外5个数为20012001、2OO22002、2OO32003、2OO42004、200520°5,它们和的个位数字是1476523的个位数3，所以原式的个位数字是3，即除以10的余数是3.【例11】求所有的质数P,使得4P21与6P21也是质数.22【解析】如果P5,则4Pl101,6p1151都是质数，所以5符合题意如果P不等于5,那么P除以5的余数为1、2、3或者4,p2除以5的余数即等于仔、22、32或者42除以5的余数，即1、4、9或者16除以5的余数，只有1和4两种情况.如果p2除以5的余数为1,那么4P21除以5的余数等于4115除以5的余数，为0，即此时4P21被5

32、整除，而4P21大于5,222所以此时4p1不是质数；如果p除以5的余数为4，同理可知6p1不是质数，所以P不等于5,4Pl与6P1至少有一个不是质数，所以只有P5满足条件.因数89909192939495969798【巩固】在图表的第二行中，恰好填上8998这因数十个数，使得每一竖列上下两个因数的乘积除以11所得的余数都是3.【解析】因为两个数的乘积除以11的余数，等于两个数分别除以W的余数之积.因此原题中的8998可以改换为110，这样上下两数的乘积除以11余3就容易计算了-我们得到下面的结果：进而得到本题的答案是：因数89909192939495969798因数37195621048因数

33、89909192939495969798因数91958997939490989296【巩固】(2000年“华杯赛”试题)3个三位数乘积的算式abcbcacab234235286(其中abe)，在校对时，发现右边的积的数字顺序出现错误，但是知道最后一位6是正确的，问原式中的ObC是多少_3【解析】由于2342352862342352868(mod9),abcbcacab(abc)(mod9),3于是(abc)8(mod9)，从而(用abc0,12,8(mod9)代入上式检验)abc2,5,8(mod9)，对a进行讨论:如果a9，那么bc2,5,8(mod9)(2)，又cab的个位数字是6，所以b

34、C的个位数字为4,bc可能为41、72、83、64,其中只有(b,c)(4,1),(8,3)符合，经检验只有983839398328245326符合题意.如果a8，那么bc3,6,0(mod9)-(3)，又bc的个位数字为2或7,则bc可能为21、43、62、76、71，其中只有(b,c)(2,1)符合，经检验，abc821不合题意.如果a7,那么bc4,7,1(mod9)(4),则bc可能为42、63，其中没有符合的(b,c).如果a6，那么b5,c4,abcbcacab700600500210000000222334586，因此这时abc不可能符合题意.综上所述，abc983是本题唯一的解

35、.例12一个大于1的数去除290,235,200时，得余数分别为a,a2,a5，则这个自然数是多少【解析】根据题意可知，这个自然数去除290,233,195时，得到相同的余数(都为a).0那么这个既然余数相同，我们可以利用余数定理，可知其中任意两数的差除以这个数肯定余自然数是29023357的约数，又是23319538的约数，因此就是57和38的公约数，因为57和38的公约数只有19和1，而这个数大于1，所以这个自然数是19.【巩固】一个大于10的自然数去除90、164后所得的两个余数的和等于这个自然数去除220后所得的余数，则这个自然数是多少【解析】这个自然数去除90、164后所得的两个余数

36、的和等于这个自然数去除90164254后所得的余数，所以254和220除以这个自然数后所得的余数相同，因此这个自然数是25422034的约数，又大于1。，这个自然数只能是17或者是34.如果这个数是34,那么它去除90、164、220后所得的余数分别是22、28、16，不符合题目条件；如果这个数是17,那么他去除90、164、220后所得的余数分别是5、11、16，符合题目条件，所以这个自然数是17.【例13】甲、乙、丙三数分别为603,939,393.某数A除甲数所得余数是A除乙数所得余数的2倍，A除乙数所得余数是A除丙数所得余数的2倍求A等于多少【解析】根据题意，这三个数除以A都有余数，则

37、可以用带余除法的形式将它们表示出来：由于*2r2,r22B，要消去余数”，我们只能先把余数处理成相同的，再两数相减.这样我们先把第二个式子乘以2，使得被除数和余数都扩大2倍，同理，第三个式子乘以4.于是我们可以得到下面的式子：603A心卅11119392A2KA1112r23934A2«3卅卅43这样余数就处理成相同的.最后两两相减消去余数，意味着能被A整除.93926031275,3934603969,1275,96951317.51的约数有1、3、17、51，其中1、3显然不满足，检验17和51可知17满足，所以A等于17.【巩固】一个自然数除429、791、500所得的余数分别

38、是a5、2a、a，求这个自然数和a的值.【解析】将这些数转化成被该自然数除后余数为2a的数：42952848,791、50021000，这样这些数被这个自然数除所得的余数都是2a，故同余将这三个数相减,得至U84879157、1000848152，所求的自然数一定是57和152的公约数，19.经过验而57,15219，所以这个自然数是19的约数，显然1是不符合条件的，那么只能是证，当这个自然数是19时，除429、791、500所得的余数分别为11、12、6,a6时成立，所以这个自然数是19,a6.【模块三：余数综合应用】【例14着名的裴波那契数列是这样的：1、1、2、3、5、8、13、21这串

39、数列当中第2008个数除以3所得的余数为多少【解析】斐波那契数列的构成规则是从第三个数起每一个数都等于它前面两个数的和，由此可以根据余数定理将裴波那契数列转换为被3除所得余数的数列：1、1、2、0、2、2、1、0、1、1、2、0第九项和第十项连续两个是1，与第一项和第二项的值相同且位置连续，所以裴波那契数列被3除的余数每8个一个周期循环出现，由于2008除以8的余数为0，所以第2008项被3除所得的余数为第8项被3除所得的余数，为0.【巩固】（2009年走美初赛六年级）有一串数：1,1,2,3,5,8,，从第三个数起，每个数都是前两个数之和，在这串数的前2009个数中，有几个是5的倍数【解析】

40、由于两个数的和除以5的余数等于这两个数除以5的余数之和再除以5的余数.所以这串数除以5的余数分别为：1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,2,3,0,可以发现这串余数中，每20个数为一个循环，且一个循环中，每5个数中第五个数是5的倍数.由于2009540卅14,所以前2009个数中，有401个是5的倍数.【例15（圣彼得堡数学奥林匹克试题）托玛想了一个正整数，并且求出了它分别除以3、6和9的余数-现知这三余数的和是15.试求该数除以18的余数.【解析】除以3、6和9的余数分别不超过2,5,8,所以这三个余数的和永远不超过25815,既然它们的和

41、等于15,所以这三个余数分别就是2,5,&所以该数加1后能被3,6,9整除，而3,6,918,设该数为a,则a18ml，即a18（m1）17（m为非零自然数），所以它除以18的余数只能为17.【巩固】（2005年香港圣公会小学数学奥林匹克试题）一个家庭，有父、母、兄、妹四人，他们任意三人的岁数之和都是3的整数倍，每人的岁数都是一个质数，四人岁数之和是100,父亲岁数最大，问：母亲是多少岁？【解析】从任意三人岁数之和是3的倍数700除以3余1,就知四个岁数都是3k1型的数，又是质数只有7，13，19，31，37，43，就容易看出：父43岁，母37岁，兄13岁，妹7岁【例16】（华杯赛试题

42、）如图，在一个圆圈上有几十个孔（不至1J100个），小明像玩跳棋那样，从A孔出发沿着逆时针方向，每隔几孔跳一步，希望一圈以后能跳回到A孔-他先试着每隔2孔跳一步，结果只能跳到B孔.他又试着每隔4孔跳一步，也只能跳到B孔-最后他每隔6孔跳一步，正好跳回到A孔，你知道这个圆圈上共有多少个孔吗？解析】设想圆圈上的孔已按下面方式编了号：A孔编号为1，然后沿逆时针方向顺次编号为2,3,4,，B孔的编号就是圆圈上的孔数.我们先看每隔2孔跳一步时，小明跳在哪些孔上？很容易看出应在1,4,7,10,上，也就是说，小明跳到的孔上的编号是3的倍数加1按题意，小明最后跳到B孔，因此总孔数是3的倍数加1同样道理，每隔

43、4孔跳一步最后跳到B孔，就意味着总孔数是5的倍数加1;而每隔6孔跳一步最后跳回到A孔，就意味着总孔数是7的倍数.如果将孔数减1,那么得数既是3的倍数也是5的倍数，因而是15的倍数,这个15的倍数加上1就等于孔数，设孔数为a，则a15ml（m为非零自然数）而且a能被7整除注意15被7除余1，所以156被7除余6，15的6倍加1正好被7整除.我们还可以看出，15的其他（小于的7）倍数加1都不能被7整除，而157105已经大于100.7以上的倍数都不必考虑，因此，总孔数只能是156191.巩固】（1997年全国小学数学奥林匹克试题）将12345678910111213依.次写到第1997个数字，组成

44、一个1997位数，那么此数除以9的余数是解析】本题第一步是要求出第1997个数字是什么，再对数字求和19共有9个数字，1099共有90个两位数，共有数字：902180（个），100999共900个三位数，共有数字：90032700（个），所以数连续写，不会写到999,从100开始是3位数，每三个数字表示一个数,（19979180）36022,即有602个三位数，第603个三位数只写了它的百位和十位从100开始的第602个三位数是701,第603个三位数是9，其中2未写出来-因为连续9个自然数之和能被9整除，所以排列起来的9个自然数也能被9整除，702个数能分成的组数是:702 9 78 (组)

45、，依次排列后，它仍然能被9整除，但702中2未写出来，所以余数为9-27【例17】设2n1是质数，证明：12,22，¥被2n1除所得的余数各不相同.22【解析】假设有两个数a>b,(1ban),它们的平方a,b被2nl除余数相同那么，由同余定理得a2b20(mod(2n1)，即(ab)(ab)0(mod(2n1)，由于2nl是质数，所以ab0(mod(2n1)或ab0(mod(2n1),由于ab,ab均小于2n1且大于0,可知，ab与2nl互质，ab也与2n1互质，即ab,ab都不能被2nl整除，产生矛盾，所以假设不成立，原题得证.【巩固】试求不大于100,且使3n7n4能被1

46、1整除的所有自然数n的和.【解析】通过逐次计算，可以求出3n被11除的余数，依次为：为3,32为9,33为5,34为4,35为1，因而3n被11除的余数5个构成一个周期：3,9,5,4,1,3,9,5,4,1,；类似地，可以求出7n被11除的余数10个构成一个周期：7,5,2,3,10,4,6,9,8,1,;于是3n7n4被11除的余数也是10个构成一个周期：3,7,0,0,4,0,8,7,5,6,：这就表明，每一个周期中，只有第3、4、6个这三个数满足题意，即n3,4,6,13,14,16,.,93,94,96时3n7n4能被3整除，所以，所有满足条件的自然数n的和为：346131416.9

47、394961343.2831480【巩固】若a为自然数，证明10侬20。5捕949).【解析】1025，由于a2°°5与短949的奇偶性相同,所以2(a2005a1949)-a2005a1949a1949(a561),如果a能被5整除，那么5a1949(a561)；如果a不能被5整除，那么a被5除的余数为1、2、3或者4,a，被5除的余数为V、24、3。、4,被5除的余数，即为1、16、81、256被5除的余数，而这四个数除以5均余1，所以不管a为多少，被5除的余数为1，而a56(a4)14，即14个a，相乘，所以a56除以5均余1，则a561能被5整除，有194956廿2

48、0051949、5a(a1)所以5(aa)由于2与5互质，所以10（a2005a1949）.【例18】设n为正整数，k2004,k被7除余数为2,k被11除余数为3,求n的最小值.【解析】2004被7除余数为2，被11除余数也为2，所以2n被7除余数为2，被11除余数为3.13由于22被7除余2,而28被7除余1，所以n除以3的余数为1;810由于2256被11除余3,21024被11除余1，所以n除以10的余数为8.可见n2是3和10的公倍数，最小为3,1030,所以n的最小值为28.【巩固】有三个连续自然数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，请写出一组这样的三

49、个连续自然数.【解析】设三个连续自然数中最小的一个为n,则其余两个自然数分别为n1,n2.依题意可知：15|n,17|n1,191n2，根据整除的性质对这三个算式进行变换：从上面可以发现2n15应为15、17、19的公倍数.由于15,17,194845，所以2n1548452k1（因为2n15是奇数），可得n4845k2415.当k1时n2430,n12431,n22432，所以其中的一组自然数为2430、2431、2432.【例19】（2008年西城实验考题）从1,2,3,，n中，任取57个数，使这57个数必有两个数的差为13,则n的最大值为多少【解析】被13除的同余序列当中，如余1的同余序

50、列，1、14、27、40、53、66，其中只要取到两个相邻的，这两个数的差为13;如果没有两个相邻的数，则没有两个数的差为13，不同的同余x序列当中不可能有两个数的差为13，对于任意一条长度为x的序列，都最多能取x个数，使得取出的数中没有两个数的差为13，即从第1个数起隔1个取1个.基于以上，门个数分成13个序列，每条序列的长度为一或-1，两个长度差为1的序列，1313要使取出的数中没有两个数的差为13，能够被取得的数的个数之差也不会超过1，所以为使57个数中任意两个数的差都不等于13，则这57个数被分配在13条序列中，在每条序列被分配的数的个数差不会超过1,那么13个序列有8个序列分配了4个

51、数，5个序列分配了5个数，则13,那么n的最大这13个序列中8个长度为8,5个长度为9，那么当n最小为8895109时，可以取出57个数，其中任两个数的差不为13，所以要使任取57个数必有两个数的差为为108【巩固】从1,2,3,4,，2007中取N个不同的数，取出的数中任意三个的和能被15整除.N最大为多少【解析】取出的N个不同的数中，任意三个的和能被15整除，则其中任意两个数除以15的余数相同，且这个余数的3倍能被15整除，所以这个余数只能是0,5或者10.在刑2007中，除以15的余数为。的有151，152,，15133,共有133个；除以15的余数为5的有1505，1515，15133

52、5，共有134个；除以15的余数为10的有15010，15110，二1513310，共有134个.所以N最大为134.【例20】将自然数1，2，3，4依次写下去，若最终写到2000,成为12彳I39992000,那么这个自然数除以99余几【解析】由于99911，可以分别求这个数除以9和11的余数，进而求出它除以99的余数-实际上求得这个数除以9和11的余数均为3,所以这个数减去3后是9和11的倍数，那么也是99的倍数，所以这个数除以99的余数为3.下面介绍另一种解法.由于100a99aa，所以100a除以99的余数等于a除以99的余数.同样，10000a,1000000a等数除以99的余数等于

53、a除以99的余数可知，一个自然数a，如果在它后面加上偶数个0,那么这个数除以99的余数等于a除以99的余数.根据这一点，可以把12A|19992000分成若干个后面带有偶数个0的数之和.由于12Ali19992000的位数是奇数，那么又寸于组成123川19992000的一位数1,2,3,9,可以分成100川00,2300|00,4500川00,6700川00,8900川00；对于其中的两位数10,11,12,98,99,可以分成1000川00,1100川00,1200川00,，9800JII00,99001|00；对于其中的三位数100,101,102,103,998,999，两两一组，可以分

54、成10010100|00,10210300|00,10410500|00,998999001100；对于其中的四位数1000,1001,1999,2000,可以分成1000001100,100100)1100,1002001100,19990000,2000.那么上面分成的所有数中，虽然每个数后面的0的个数互不相同，但都是偶数个，且它们的和恰好为123|119992000,那么123川19992000除以99的余数就等于分成的这些数除以99的余数的和.由于这些数除以99的余数分别为1,23,45,67,89;10,11,12,，98,99;100101,102103,104105,998999

55、;1000,1001,1999,2000，而其中100101,102103,104105,，998999是公差为2002的等差数列，共450项，可知所有这些余数的和为：248804130,248804130201除以99的余数，为3.所以123|19992000除以99的余数为3.【巩固】将1至2008这2008个自然数，按从小到大的次序依次写出，得一个多位数：试求这个多位数除以9的余数.【解析】以这个八位数为例，它被9除的余数等于19992000被9除的余数，但是由于1999与1999被9除的余数相同，2000与2000被9除的余数相同，所以就与19992000被9除的余数相同.由此可得，从1开始的自然数被9除的余数与前2008个自然数之和除以9的余数相同.120082008根据等差数列求和公式,这个和为：2017036，它被9除的余数为1.2另外还可以利用连续9个自然数之和必能被9整除这个性质，将原多位数分成，2008等数，可见它被9除的余数与2008被9除的余数相同.因此，此数被9除的余数为1.【例21】（2008年清华附中考题）已知n是正整数，规定n!12川n,令m1!12!23!3川2007!2007，则整数m除以2008的余数为多少【解析】m1!12!