（趣味奥数）第十八讲 同余问题-六年级下册奥数精讲精练（通用版）

第十八讲 同余问题 神秘岛屿的宝石谜题 在遥远的海域，有一座神秘的岛屿，传说岛上藏有无数宝藏。探险家小辉和小敏听闻后，决定一同前往探寻。经过漫长的航行，他们终于登上了这座神秘岛屿。 在岛屿的深处，他们发现了一个古老的洞穴。进入洞穴后，他们看到了一个巨大的宝箱，宝箱上刻满了奇怪的符号和文字。正当他们疑惑之际，洞穴中突然响起了一个神秘的声音：“想要打开宝箱，就必须解开关于宝石数量的谜题。” 神秘声音说道：“如果将宝箱中的宝石每 4 个一组进行分组，最后会剩下 3 个；每 6 个一组进行分组，最后同样剩下 3 个。你们能算出宝箱中最少有多少颗宝石吗？” 小辉和小敏立刻开始思考。小敏反应迅速，说道：“这是同余问题中余数相同的情况。4 和 6 的最小公倍数可以通过分解质因数来求，4 = 2×2，6 = 2×3，所以它们的最小公倍数是 2×2×3 = 12。再加上相同的余数 3，那么宝箱中最少有 12 + 3 = 15 颗宝石。” 神秘声音发出一阵低沉的笑声，宝箱上的一个符号亮起，似乎在表示回答正确。 接着，神秘声音又给出了新的谜题：“现在，如果把宝石每 5 个一组进行分组，剩下 2 个；每 7 个一组进行分组，剩下 4 个。你们能算出此时宝石至少有多少颗吗？” 小辉皱着眉头思考片刻，说道：“虽然余数不同，但我们可以尝试转化。5 - 2 = 3，7 - 4 = 3，这意味着如果宝石再多 3 颗，就能被 5 和 7 整除。5 和 7 是互质数，它们的最小公倍数是 5×7 = 35，所以原来宝石至少有 35 - 3 = 32 颗。” 神秘声音再次响起笑声，宝箱上又一个符号亮起。 最后，神秘声音说出了最难的谜题：“将宝石每 9 个一组进行分组，剩下 5 个；每 11 个一组进行分组，剩下 7 个。算出宝石的数量，你们就能打开宝箱。” 小辉和小敏全神贯注地思考着。过了好一会儿，小辉兴奋地说：“设宝石数量为 x，根据题意列出同余方程 x ≡ 5 (mod 9)，x ≡ 7 (mod 11)。从第一个方程可得 x = 9a + 5（a 为整数），代入第二个方程 9a + 5 ≡ 7 (mod 11)，即 9a ≡ 2 (mod 11)。因为 9 和 11 互质，通过尝试，9 乘以 6 等于 54，54÷11 = 4……10，9 乘以 7 等于 63，63÷11 = 5……8，9 乘以 8 等于 72，72÷11 = 6……6，9 乘以 9 等于 81，81÷11 = 7……4，9 乘以 10 等于 90，90÷11 = 8……2，所以 a = 10。那么 x = 9×10 + 5 = 95，再验证 95÷11 = 8……7，符合条件，所以宝石有 95 颗。” 随着小辉的回答结束，宝箱发出一阵耀眼的光芒，缓缓打开，里面堆满了闪闪发光的宝石。小辉和小敏带着这些珍贵的宝石，结束了这次充满挑战和惊喜的神秘岛屿之旅，也对同余问题有了更深刻的理解和掌握。 同余这个概念最初是由伟大的德国数学家高斯发现的。同余的定义是这样的： 两个整数a，b，如果它们除以同一自然数m所得的余数想同，则称a，b对于模m同余。记作：a≡b（mod　ｍ）。读做：ａ同余于ｂ模ｍ。比如，12除以5，47除以5，它们有相同的余数2，这时我们就说，对于除数5，12和47同余，记做12≡47（mod　5）。 同余的性质比较多，主要有以下一些： 性质（1）：对于同一个出书，两个数之和（或差）与它们的余数之和（或差）同余。比如：32除以5余数是2，19除以5余数是4，两个余数的和是2+4=6。“32+19”除以5的余数就恰好等于它们的余数和6除以5的余数。也就是说，对于除数5，“32+19”与它们的余数和“2+4”同余，用符号表示就是：32≡2（mod　5），19≡4（mod　5），32+19≡2+4≡1（mod　5） 性质（2）：对于同意个除数，两个数的乘积与它们余数的乘积同余。 性质（3）：对于同意个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。 性质（4）：对于同意个除数，如果两个整数同余，那么它们的乘方仍然同余。 应用同余性质几萼体的关键是要在正确理解的基础上灵活运用同余性质。把求一个较大的数除以某数的余数问题转化为求一个较小的数除以这个数的余数，使复杂的题变简单，使困难的题变容易。 1： 设是质数，证明：，，…，被除所得的余数各不相同。 【思路分析】 若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m整除；根据同余定理解题即可。 【标准答案】 假设有两个数、，（），它们的平方，被除余数相同。那么，由同余定理得，即，由于是质数，所以或，由于，均小于且大于0，可知，与互质，也与互质，即，都不能被整除，产生矛盾，所以假设不成立，原题得证。 1. 1．从1，2，3，…，n中，任取57个数，使这57个数必有两个数的差为13，则n的最大值为多少？ 2．在3×3的方格表中已如右图填入了9个质数。将表中同一行或同一列的3个数加上相同的自然数称为一次操作。问：你能通过若干次操作使得表中9个数都变为相同的数吗？为什么？ 2 3 5 13 11 7 17 19 23 3．有一个自然数，它除以、、所得到的商（＞）与余数（＞）之和都相等，这样的数最小可能是多少。 2： 两位自然数与除以7都余1，并且，求。 【思路分析】 根据两个自然数除以7的余数相同，可以得到两个数的差是7的倍数；能被7整除，即能被7整除。所以只能有，那么可能为92和81，验算可得当时，满足题目要求，。 【标准答案】 根据分析可得： 当时，满足题目要求， 2． 1．有一个大于1的整数，它除967，1000，2001得到相同的余数，那么这个整数是多少？ 2．140，225，293同时除以某一个自然数得到的余数相同，试问这个自然数是多少？余数又是多少？ 3．已知三个数127,99和一个小于30的两位数a除以一个一位数b的余数都是3,求a和b的值. 3： 盒乒乓球,每次8个8个地数,10个10个地数,12个12个地数,最后总是剩下3个.这盒乒乓球至少有多少个？ 【思路分析】 试题分析：根据题意，找出8、10、12的最小公倍数，然后加3． 理解8个8个地数，10个10个地数，12个12个的数都正好无剩余，也就是这盒乒乓球减少3个后是8，10，12的公倍数． 3． 1．有一个大于1的数，除45，59，101所得的余数相同，求这个数可能是多少？ 2．若干个数排成一行，开头的两个数是1和3，从第二个数开始，每个数的4倍等于它左右两边两数之和． （1）求这个数列中第80个数和第123个数被3除的余数各是多少？ （2）请问1785是否在此数列中？ 3．把1到2002这2002个自然数依次写下来，得到一个多位数1234567891011…20012002，试求这一多位数除以9的余数． 4： 斐波那契数列定义如下：前两个数都是1，从第三个数起，每个数是前面两个数的和。于是其中前面几个数是1，1，2，3，5，8，13，21，34，55… （1）求其中第2002个数被4除的余数。 （2）如果在前n个数中有2002个是4的倍数，问n应是多少？ 【思路分析】 我们只需考虑斐波那契数列的前两个数被4除的余数，后面其他数被4除的余数可根据斐波那契数列的构成规律得到。 例如：第一个数1被4除余1，第二个数1被4除余1，那么第三个数被4除的余数就是前两个余数的和，被4除的余数为2，第四个数被4除的余数就是第二个数被4除的余数1与第三个数被4除的余数2的和，被4除的余数为3。 因此斐波那契数列中前若干个数被4除的余数依次为： 1，1，2，3，1，0，1，1，2，3，1，0… 可以发现其中的规律是每6位是循环重复的，到此问题便可解决。 【标准答案】 （1）由于2002＝6×333＋4，而第四个余数是3，所以第2002个数被4除余3。 （2）6×2002＝12012 6×2003＝12018 即n的值可能是12012、12013、12014、12015、12016、12017。 4. 1．著名的斐波那契数列是这样的“1、1、2、3、5、8、13、21……”这串数列当中第2008个数除以3所得的余数为多少？ 2．甲、乙、丙、丁四个旅行团分别有游客69人、85人、93人、97人．现在要把这四个旅行团分别进行分组，使每组是A名游客，以便乘车前往参观游览．已知甲、乙、丙三个旅行团分成每组A人的若干组后，所剩的人数都相同，问丁旅行团分成每组A人的若干组后还剩几人？ 3．设的各位数字之和为，的各位数字之和为，的各位数字之和为，的各位数字之和为，那么？ 高斯有多伟大 同余这个概念最初是由伟大的德国数学家高斯发现的。 高斯 （Gauss, Carl Friedrich, 1777-1855） ,德国数学家，科学家，他幼年时就表现出超人的数学天才。和牛顿、阿基米德，被誉为有史以来的三大数学家。高斯是近代数学奠基者之一，在历史上影响之大， 可以和阿基米德、牛顿、欧拉并列，有“数学王子”之称。高斯的数学研究几乎遍及所有领域，在数论、代数学、非欧几何、复变函数和微分几何等方面都做出了开创性的贡献。他还把数学应用于天文学、大地测量学和磁学的研究，发明了最小二乘法原理。高斯的数论研究总结在《算术研究》（1801）中，这本书奠定了近代数论的基础，它不仅是数论方面的划时代之作，也是数学史上不可多得的经典著作之一。高斯对当代数学的重要贡献是证明了代数基本定理，他的存在性证 明开创了数学研究的新途径。 高斯一生共发表155篇论文，他对待学问十分严谨，其着作有《地磁概念》和《论与距离平方成反比的引力和斥力的普遍定律》（1840）等。 1： 设是质数，证明：，，…，被除所得的余数各不相同。 【思路分析】 若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m整除；根据同余定理解题即可。 【标准答案】 假设有两个数、，（），它们的平方，被除余数相同。那么，由同余定理得，即，由于是质数，所以或，由于，均小于且大于0，可知，与互质，也与互质，即，都不能被整除，产生矛盾，所以假设不成立，原题得证。 1. 1．从1，2，3，…，n中，任取57个数，使这57个数必有两个数的差为13，则n的最大值为多少？ 答案：108 分析：若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m整除；根据同余定理进行论证解题即可。 详解：被13除的同余序列当中，如余1的同余序列，1、14、27、40、53、66…，其中只要取到两个相邻的，这两个数的差为13；如果没有两个相邻的数，则没有两个数的差为13，不同的同余序列当中不可能有两个数的差为13，对于任意一条长度为x的序列，都最多能取个数，使得取出的数中没有两个数的差为13，即从第1个数起隔1个取1个。 基于以上，n个数分成13个序列，每条序列的长度为或，两个长度差为1的序列，要使取出的数中没有两个数的差为13，能够被取得的数的个数之差也不会超过1，所以为使57个数中任意两个数的差都不等于13，则这57个数被分配在13条序列中，在每条序列被分配的数的个数差不会超过1，那么13个序列有8个序列分配了4个数，5个序列分配了5个数，则这13个序列中8个长度为8，5个长度为9，那么当n最小为时，可以取出57个数，其中任两个数的差不为13，所以要使任取57个数必有两个数的差为13，那么n的最大值为108。 点睛：正确理解同余定理的意义，是解答此题的关键，运用同余定理解题即可。 2．在3×3的方格表中已如右图填入了9个质数。将表中同一行或同一列的3个数加上相同的自然数称为一次操作。问：你能通过若干次操作使得表中9个数都变为相同的数吗？为什么？ 2 3 5 13 11 7 17 19 23 答案：见详解 分析：若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m整除；根据同余定理进行论证解题即可。 详解：因为表中9个质数之和恰为100，被3除余1，经过每一次操作，总和增加3的倍数，所以表中9个数之和除以3总是余1；如果表中9个数变为相等，那么9个数的总和应能被3整除，这就得出矛盾。所以，无论经过多少次操作，表中的数都不会变为9个相同的数。 点睛：正确理解同余定理的意义，是解答此题的关键。 3．有一个自然数，它除以、、所得到的商（＞）与余数（＞）之和都相等，这样的数最小可能是多少。 答案： 分析：首先抓住余数与商的和相同，设出这个未知数，进一步设出三个数的商，表示出三个数，找出三个数的商之间的关系，设出三个数的公约数，利用余数之间的关系求得三个数的商，由此分析得出结论。 详解： 至少为， 至少为， 至少为， 最小为1081。 点睛：此题考查利用有余数的除法，抓住商、余数、除数、被除数之间的关系和最大公约数等知识综合性的解决问题。 2： 两位自然数与除以7都余1，并且，求。 【思路分析】 根据两个自然数除以7的余数相同，可以得到两个数的差是7的倍数；能被7整除，即能被7整除。所以只能有，那么可能为92和81，验算可得当时，满足题目要求，。 【标准答案】 根据分析可得： 当时，满足题目要求， 2． 1．有一个大于1的整数，它除967，1000，2001得到相同的余数，那么这个整数是多少？ 答案：11 详解：所求整数应能整除 967，1000，2001的两两之差，即 1000-967＝33＝3×11， 2001-1000＝1001＝7×11×13， 2001-967＝1034＝2×11×47. 这个整数是这三个差的公约数11. 答：这个整数是11. 2．140，225，293同时除以某一个自然数得到的余数相同，试问这个自然数是多少？余数又是多少？ 答案：17  4 3．已知三个数127,99和一个小于30的两位数a除以一个一位数b的余数都是3,求a和b的值. 答案：B=4    A可能是11、15、19、23、27． 3： 盒乒乓球,每次8个8个地数,10个10个地数,12个12个地数,最后总是剩下3个.这盒乒乓球至少有多少个？ 【思路分析】 试题分析：根据题意，找出8、10、12的最小公倍数，然后加3． 理解8个8个地数，10个10个地数，12个12个的数都正好无剩余，也就是这盒乒乓球减少3个后是8，10，12的公倍数． 3． 1．有一个大于1的数，除45，59，101所得的余数相同，求这个数可能是多少？ 答案：2、7、14 2．若干个数排成一行，开头的两个数是1和3，从第二个数开始，每个数的4倍等于它左右两边两数之和． （1）求这个数列中第80个数和第123个数被3除的余数各是多少？ （2）请问1785是否在此数列中？ 答案：（1）0  2    （2）不在 详解：先写出此数列的前几项：1，3，11，41，153，571，2131，7953，… 每一项被3除的余数组成的数列为：1，0，2，2，0，1，1，0，… 这是一列以1，0，2，2，0，1六个余数为一循环的数列，由80÷6=13余2，所以第80项被3除余0；由123÷6=20余3，所以第123项被3除余数是2． 对1785是否在此列中，我们有两种方法： （1）因为这个数列是逐渐增大的，而571和2131是相邻的两项，所以1785不在此数列中． （2）将每一项被5除的余数组成的数列为：1，3，1，1，3，1，1，3，… 这是一列以1，3，1三个数一循环的数列，由于1785≡0 mod(5)，所以1785不在此数列中． 3．把1到2002这2002个自然数依次写下来，得到一个多位数1234567891011…20012002，试求这一多位数除以9的余数． 答案：1 分析：从一个数被9除的特征可以知道，一个自然数除以9的余数，与这个自然数各个数位上的数字和除以9的余数正好相同．如此一来，求一个多位数除以9的余数就转化为1到2002这2002个自然数中，所有数字之和是多少的问题．但这还不够，有这样一个规律：一个多位数被9除的余数，可以根据情况在适当的地方把这个多位数断开，然后把每一段的数加起来，这个和被9除的余数，就是这个多位数被9除的余数． 详解：我们可以把多位数1234567891011…20012002断开1，2，3，4，…，2001，2002，而 1+2+3+4+…+2001+2002=（1+2002）×2002÷2=2003×2002÷2=2003×1001 由于2003≡5 mod(9),1001≡2 mod(9) 所以2003×1001≡5×2 mod(9)，即2003×1001≡1 mod(9)，从而多位数1234567891011…20012002被9除余1． 4： 斐波那契数列定义如下：前两个数都是1，从第三个数起，每个数是前面两个数的和。于是其中前面几个数是1，1，2，3，5，8，13，21，34，55… （1）求其中第2002个数被4除的余数。 （2）如果在前n个数中有2002个是4的倍数，问n应是多少？ 【思路分析】 我们只需考虑斐波那契数列的前两个数被4除的余数，后面其他数被4除的余数可根据斐波那契数列的构成规律得到。 例如：第一个数1被4除余1，第二个数1被4除余1，那么第三个数被4除的余数就是前两个余数的和，被4除的余数为2，第四个数被4除的余数就是第二个数被4除的余数1与第三个数被4除的余数2的和，被4除的余数为3。 因此斐波那契数列中前若干个数被4除的余数依次为： 1，1，2，3，1，0，1，1，2，3，1，0… 可以发现其中的规律是每6位是循环重复的，到此问题便可解决。 【标准答案】 （1）由于2002＝6×333＋4，而第四个余数是3，所以第2002个数被4除余3。 （2）6×2002＝12012 6×2003＝12018 即n的值可能是12012、12013、12014、12015、12016、12017。 4. 1．著名的斐波那契数列是这样的“1、1、2、3、5、8、13、21……”这串数列当中第2008个数除以3所得的余数为多少？ 答案：0 分析：从这列数的第二项开始是：1、2、3、5、8、13、21、34、55……，从第二项开始，这列数除以3的余数分别是：1、2、0、2、2、1、0、1、1、2、0……由此即可知道8个数一循环，根据周期问题的方式，即第2008个数的余数：（2008－1）÷8＝250……1，由此即可知道它的余数是0。 详解：由分析可知：从第二个数开始这些数除以3的余数是8个数一循环，即1、2、0、2、2、1、0、1 （2008－1）÷8 ＝2007÷8 ＝250（组）……7个 这个周期第七个数的余数是0。 答：这串数列当中第2008个数除以3所得的余数为0。 点睛：本题主要考查周期问题，找到这列数的周期是解题的关键。 2．甲、乙、丙、丁四个旅行团分别有游客69人、85人、93人、97人．现在要把这四个旅行团分别进行分组，使每组是A名游客，以便乘车前往参观游览．已知甲、乙、丙三个旅行团分成每组A人的若干组后，所剩的人数都相同，问丁旅行团分成每组A人的若干组后还剩几人？ 答案：1人 详解：如果a，b除以c的余数相同，那么a与b的差能被c整除． 此题是第四届小数报数学竞赛决赛试题．因为在一些题目中因为余数的存在，不便于我们计算，去掉余数，回到比较熟悉的整除性问题，那么问题就会变得简单了． 详解过程：由85-69=16，93-85=8，推出A=8或4或2，所以丁团分成每组A人的若干组后还剩1人． 3．设的各位数字之和为，的各位数字之和为，的各位数字之和为，的各位数字之和为，那么？ 答案：5 分析：根据同余概念进行解答即可。 详解：由于一个数除以9的余数与它的各位数字之和除以9的余数相同，所以与、、、除以9都同余，而2009除以9的余数为2，则除以9的余数与除以9的余数相同，而除以9的余数为1，所以除以9的余数为除以9的余数，即为5。 另一方面，由于，所以的位数不超过8036位，那么它的各位数字之和不超过，即；那么的各位数字之和，的各位数字之和，小于18且除以9的余数为5，那么为5或14，的各位数字之和为5，即。 点睛：本题考查同余定理，解答本题的关键是掌握同余定理的概念。 学科网（北京）股份有限公司 $$