发布时间 : 星期六 文章小学五年级奥数—数论之同余问题更新完毕开始阅读
以这个自然数是19，a?6.
【模块三：余数综合应用】
【例 14】 著名的裴波那契数列是这样的：1、1、2、3、5、8、13、21??这串数列当中第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的倍数？
【解析】 由于两个数的和除以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的倍数．由于2009?5?401?4，所以前2009个数中，有401个是5的倍数．
【例 15】 (圣彼得堡数学奥林匹克试题)托玛想了一个正整数，并且求出了它分别除以3、6和9的余数．现
知这三余数的和是15．试求该数除以18的余数．
【解析】 除以3、6和9的余数分别不超过2，5，8，所以这三个余数的和永远不超过2?5?8?15，
既然它们的和等于15，所以这三个余数分别就是2，5，8．所以该数加1后能被3，6，9整除，而[3,6,9]?18，设该数为a，则a?18m?1，即a?18(m?1)?17（m为非零自然数），所以它除以18的余数只能为17．
【巩固】 (2005年香港圣公会小学数学奥林匹克试题)一个家庭，有父、母、兄、妹四人，他们任意三人
的岁数之和都是3的整数倍，每人的岁数都是一个质数，四人岁数之和是100，父亲岁数最大，问：母亲是多少岁?
【解析】 从任意三人岁数之和是3的倍数，100除以3余1，就知四个岁数都是3k?1型的数，又是质数．只
有7，13，19，31，37，43，就容易看出：父43岁，母37岁，兄13岁，妹7岁．
【例 16】 (华杯赛试题)如图，在一个圆圈上有几十个孔(不到100个)，小明像玩跳棋 BA那样，从A孔出发沿着逆时针方向，每隔几孔跳一步，希望一圈以后能跳回到A孔．他先试着每隔2孔跳一步，结果只能跳到B孔．他又试着每隔4孔跳一步，也只能跳到B孔．最后他每隔6孔跳一步，正好跳回到A孔，你知道这个圆圈上共有多少个孔吗?
【解析】 设想圆圈上的孔已按下面方式编了号：A孔编号为1，然后沿逆时针方向顺次编号
为2，3，4，?，B孔的编号就是圆圈上的孔数．
我们先看每隔2孔跳一步时，小明跳在哪些孔上?很容易看出应在1，4，7，10，?上，也就是说， 1．
同样道理，每隔4孔跳一步最后跳到B孔，就意味着总孔数是5的倍数加1；而每隔6孔跳一步最后跳回到A孔，就意味着总孔数是7的倍数．
如果将孔数减1，那么得数既是3的倍数也是5的倍数，因而是15的倍数．这个15的倍数加上1 就等于孔数，设孔数为a，则a?15m?1（m为非零自然数）而且a能被7整除．注意15被7除余1，所以15?6被7除余6，15的6倍加1正好被7整除．我们还可以看出，15的其他(小于的7)倍数加1都不能被7整除，而15?7?105已经大于100．7以上的倍数都不必考虑，因此，总孔数只能是15?6?1?91．
【巩固】 (1997年全国小学数学奥林匹克试题)将12345678910111213......依次写到第1997个数字，组成一
个1997位数，那么此数除以9的余数是 ________．
【解析】 本题第一步是要求出第1997个数字是什么，再对数字求和．
1～9共有9个数字，10～99共有90个两位数，共有数字：90?2?180 (个), 100～999共900
小明跳到的孔上的编号是3的倍数加1．按题意，小明最后跳到B孔，因此总孔数是3的倍数加
个三位数，共有数字：900?3?2700 (个),所以数连续写，不会写到999,从100开始是3位数，每三个数字表示一个数，(1997?9?180)?3?602......2，即有602个三位数，第603个三位数只写了它的百位和十位．从100开始的第602个三位数是701，第603个三位数是9，其中2未写出来．因为连续9个自然数之和能被9整除，所以排列起来的9个自然数也能被9整除，702个数能分成的组数是：702?9?78 (组)，依次排列后，它仍然能被9整除，但702中2未写出来，所以余数为9-2?7 ．
【例 17】 设2n?1是质数，证明：12，22，?，n2被2n?1除所得的余数各不相同．
【解析】 假设有两个数a、b，(1?b?a?n)，它们的平方a2，b2被2n?1除余数相同．那么，由
同余定理得a2?b2?0(mod(2n?1))，即(a?b)(a?b)?0(mod(2n?1))，由于2n?1是质数，所以由于a?b，可知，a?b?0(mod(2n?1))或a?b?0(mod(2n?1))，a?b均小于2n?1且大于0，a?b与2n?1互质，a?b也与2n?1互质，即a?b，a?b都不能被2n?1整除，产生矛盾，所以假设不成立，原题得证．
【巩固】 试求不大于100，且使3n?7n?4能被11整除的所有自然数n的和． 【解析】 通过逐次计算，可以求出3n被11除的余数，
依次为：31为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，……； 于是3n?7n?4被11除的余数也是10个构成一个周期：3，7，0，0，4，0，8，7，5，6，……； 这就表明，每一个周期中，只有第3、4、6个这三个数满足题意， 即n?3,4,6,13,14,16,......,93,94,96时3n?7n?4能被11整除，所以， 所有满足条件的自然数n的和为：
3?4?6?13?14?16?...?93?94?96?13?43?...?283?1480．
【巩固】 若a为自然数，证明10(a2005?a1949)．
2005?a1949)． 【解析】 10?2?5，由于a2005与a1949的奇偶性相同，所以2(aa2005?a1949?a1949(a56?1)，如果a能被5整除，那么5a1949(a56?1)；如果a不能被5整除，那么a被5除的余数为1、2、3或者4，a4被5除的余数为14、24、34、44被5除的余数，即为1、16、81、256被5除的余数，而这四个数除以5均余1，所以不管a为多少，a4被5除的余数为1，而a56?(a4)14，即14个a4相乘，所以a56除以5均余1，则a56?1能被5整除，有5a1949(a56?1)．所以5(a2005?a1949)．
由于2与5互质，所以10(a2005?a1949)．
【例 18】 设n为正整数，k?2004n，k被7除余数为2，k被11除余数为3，求n的最小值． 【解析】 2004被7除余数为2，被11除余数也为2，所以2n被7除余数为2，被11除余数为3．
由于21?2被7除余2，而23?8被7除余1，所以n除以3的余数为1； 由于28?256被11除余3，210?1024被11除余1，所以n除以10的余数为8． 可见n?2是3和10的公倍数，最小为?3,10??30，所以n的最小值为28．
【巩固】 有三个连续自然数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，请写
出一组这样的三个连续自然数．
【解析】 设三个连续自然数中最小的一个为n，则其余两个自然数分别为n?1，n?2．
依题意可知：15|n，17|?n?1?，19|?n?2?，根据整除的性质对这三个算式进行变换：
?15|?2n?15???17|?n?1??17|?2n?2??17|?2n?15???[15,17,19]|?2n?15? 19|?n?2??19|?2n?4??19|?2n?15???15|n?15|2n从上面可以发现2n?15应为15、17、19的公倍数．
由于[15,17,19]?4845，所以2n?15?4845?2k?1? (因为2n?15是奇数)，可得n?4845k?2415． 当k?1时n?2430，n?1?2431，n?2?2432，所以其中的一组自然数为2430、2431、2432．
【例 19】 (2008年西城实验考题)从1，2，3，??，n中，任取57个数，使这57个数必有两个数的差
为13，则n的最大值为多少？
【解析】 被13除的同余序列当中，如余1的同余序列，1、14、27、40、53、66……，其中只要取到两个
相邻的，这两个数的差为13；如果没有两个相邻的数，则没有两个数的差为13，不同的同余序列当中不可能有两个数的差为13，对于任意一条长度为x的序列，都最多能取x???个数，使
2???x?得取出的数中没有两个数的差为13，即从第1个数起隔1个取1个． 基于以上，n个数分成13个序列，每条序列的长度为??n??n?或?13??1，两个长度差为1的序列，?13????要使取出的数中没有两个数的差为13，能够被取得的数的个数之差也不会超过1，所以为使57个数中任意两个数的差都不等于13，则这57个数被分配在13条序列中，在每条序列被分配的数的个数差不会超过1，那么13个序列有8个序列分配了4个数，5个序列分配了5个数，则这13个序列中8个长度为8，5个长度为9，那么当n最小为8?8?9?5?109时，可以取出57个数，其中任两个数的差不为13，所以要使任取57个数必有两个数的差为13，那么n的最大值为108．
【巩固】 从1，2，3，4，?，2007中取N个不同的数，取出的数中任意三个的和能被15整除．N最大为
多少？
【解析】 取出的N个不同的数中，任意三个的和能被15整除，则其中任意两个数除以15的余数相同，且
这个余数的3倍能被15整除，所以这个余数只能是0，5或者10．在1?2007中，除以15的余数为0的有15?1，…，共有133个；除以15的余数为5的有15?0?5，…，15?2，15?133，15?1?5，
15?133?5，共有134个；除以15的余数为10的有15?0?10，15?1?10，…，15?133?10，
共有134个．所以N最大为134．
【例 20】 将自然数1，2，3，4??依次写下去，若最终写到2000，成为123?19992000，那么这个自然
数除以99余几？