小学五年级奥数—数论之同余问题

数论之同余问题 余数问题是数论知识板块中另一个内容丰富 题目难度较大的知识体系 也是各大杯赛小升初考试 必考的奥数知识点 所以学好本讲对于学生来说非常重要 许多孩子都接触过余数的有关问题 并有不少孩子说 遇到余数的问题就基本晕菜了 余数问题主要包括了带余除法的定义 三大余数定理 加法余数定理 乘法余数定理 和同余定理 及中国剩余定理和有关弃九法原理的应用 知识点拨 一 带余除法的定义及性质 一 带余除法的定义及性质 一般地 如果 a 是整数 b 是整数 b 0 若有 a b q r 也就是 a b q r 0 r b 我们称上面的除法算式为一个带余除法算式 这里 1 当时 我们称 a 可以被 b 整除 q 称为 a 除以 b 的商或完全商0r 2 当时 我们称 a 不可以被 b 整除 q 称为 a 除以 b 的商或不完全商0r 一个完美的带余除法讲解模型 如图 这是一堆书 共有 a 本 这个 a 就可以理解为被除数 现在要求按照 b 本一捆打包 那么 b 就是除数的角色 经过打包后 共打包了 c 捆 那么这个 c 就是商 最后还剩余 d 本 这个 d 就是 余数 这个图能够让学生清晰的明白带余除法算式中 4 个量的关系 并且可以看出余数一定要比除数小 二 三大余数定理 二 三大余数定理 1 1 余数的加法定理余数的加法定理 a 与 b 的和除以 c 的余数 等于 a b 分别除以 c 的余数之和 或这个和除以 c 的余数 例如 23 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 2 余数的乘法定理余数的乘法定理 a 与 b 的乘积除以 c 的余数 等于 a b 分别除以 c 的余数的积 或者这个积除以 c 所得的余数 例如 23 16 除以 5 的余数分别是 3 和 1 所以 23 16 除以 5 的余数等于 3 1 3 当余数的和比除数大时 所求的余数等于余数之积再除以 c 的余数 例如 23 19 除以 5 的余数分别是 3 和 4 所以 23 19 除以 5 的余数等于 3 4 除以 5 的余数 即 2 3 3 同余定理同余定理 若两个整数 a b 被自然数 m 除有相同的余数 那么称 a b 对于模 m 同余 用式子表示为 a b mod m 左边的式子叫做同余式 同余式读作 a 同余于 b 模 m 由同余的性质 我们可以得到一个非常重要的推论 若两个数 a b 除以同一个数 m 得到的余数相同 则 a b 的差一定能被 m 整除 用式子表示为 如果有 a b mod m 那么一定有 a b mk k 是整数 即 m a b 三 弃九法原理 三 弃九法原理 在公元前 9 世纪 有个印度数学家名叫花拉子米 写有一本 花拉子米算术 他们在计算时通常是 在一个铺有沙子的土板上进行 由于害怕以前的计算结果丢失而经常检验加法运算是否正确 他们的检 验方式是这样进行的 例如 检验算式1234 1898178902889923 1234 除以 9 的余数为 1 1898 除以 9 的余数为 8 18922 除以 9 的余数为 4 除以 9 的余数为 7 除以 9 的余数为 0 这些余数的和除以 9 的余数为 2 而等式右边和除以 9 的余数为 3 那么上面这个算式一定是错的 上述检验方法恰好用到的就是我们前面所讲的余数的加法定理 即如果这个等式是正确的 那么左 边几个加数除以 9 的余数的和再除以 9 的余数一定与等式右边和除以 9 的余数相同 而我们在求一个自然数除以 9 所得的余数时 常常不用去列除法竖式进行计算 只要计算这个自然 数的各个位数字之和除以 9 的余数就可以了 在算的时候往往就是一个 9 一个 9 的找并且划去 所以这 种方法被称作 弃九法 所以我们总结出弃九发原理 任何一个整数模 9 同余于它的各数位上数字之和 以后我们求一个整数被 9 除的余数 只要先计算这个整数各数位上数字之和 再求这个和被 9 除的 余数即可 利用十进制的这个特性 不仅可以检验几个数相加 对于检验相乘 相除和乘方的结果对不对同样 适用 注意 弃九法只能知道原题一定是错的或有可能正确 但不能保证一定正确 例如 检验算式 9 9 9 时 等式两边的除以 9 的余数都是 0 但是显然算式是错误的 但是反过来 如果一个算式一定是正确的 那么它的等式 2 两端一定满足弃九法的规律 这个思想 往往可以帮助我们解决一些较复杂的算式迷问题 四 中国剩余定理 四 中国剩余定理 1 1 中国古代趣题 中国古代趣题 中国数学名著 孙子算经 里有这样的问题 今有物 不知其数 三三数之 剩二 五五数之 剩三 七七数之 剩二 问物几何 答曰 二十三 此类问题我们可以称为 物不知其数 类型 又被称为 韩信点兵 韩信点兵又称为中国剩余定理 相传汉高祖刘邦问大将军韩信统御兵士多少 韩信答说 每 3 人一 列余 1 人 5 人一列余 2 人 7 人一列余 4 人 13 人一列余 6 人 刘邦茫然而不知其数 我们先考虑下列的问题 假设兵不满一万 每 5 人一列 9 人一列 13 人一列 17 人一列都剩 3 人 则兵有多少 首先我们先求 5 9 13 17 之最小公倍数 9945 注 因为 5 9 13 17 为两两互质的整数 故其 最小公倍数为这些数的积 然后再加 3 得 9948 人 孙子算经的作者及确实著作年代均不可考 不过根据考证 著作年代不会在晋朝之后 以这个考证 来说上面这种问题的解法 中国人发现得比西方早 所以这个问题的推广及其解法 被称为中国剩余定 理 中国剩余定理 Chinese Remainder Theorem 在近代抽象代数学中占有一席非常重要的地位 2 2 核心思想和方法 核心思想和方法 对于这一类问题 我们有一套看似繁琐但是一旦掌握便可一通百通的方法 下面我们就以 孙子算 经 中的问题为例 分析此方法 今有物 不知其数 三三数之 剩二 五五数之 剩三 七七数之 剩二 问物几何 题目中我们可以知道 一个自然数分别除以 3 5 7 后 得到三个余数分别为 2 3 2 那么我们首 先构造一个数字 使得这个数字除以 3 余 1 并且还是 5 和 7 的公倍数 先由 即 5 和 7 的最小公倍数出发 先看 35 除以 3 余 2 不符合要求 那么就继续看 55 735 和 7 的 下一个 倍数是否可以 很显然 70 除以 3 余 135 270 类似的 我们再构造一个除以 5 余 1 同时又是 3 和 7 的公倍数的数字 显然 21 可以符合要求 最后再构造除以 7 余 1 同时又是 3 5 公倍数的数字 45 符合要求 那么所求的自然数可以这样计 算 其中 k 是从 1 开始的自然数 2 703 212 45 3 5 7 233 3 5 7 kk 也就是说满足上述关系的数有无穷多 如果根据实际情况对数的范围加以限制 那么我们就能找到 所求的数 例如对上面的问题加上限制条件 满足上面条件最小的自然数 那么我们可以计算得到所求2 703 212 452 3 5 7 23 如果加上限制条件 满足上面条件最小的三位自然数 我们只要对最小的 23 加上 3 5 7 即可 即 23 105 128 例题精讲 模块一 带余除法的定义和性质 例 1 第五届小学数学报竞赛决赛第五届小学数学报竞赛决赛 用某自然数用某自然数去除去除 得到商是 得到商是 4646 余数是 余数是 求 求和和 a1992rar 解析解析解析解析 因为是的倍还多 得到 得 所以 1992a46r19924643 14 1992464314 43a 14r 巩固巩固巩固巩固 清华附中小升初分班考试清华附中小升初分班考试 甲 乙两数的和是甲 乙两数的和是 甲数除以乙数商 甲数除以乙数商余余 求甲 乙两数 求甲 乙两数 10881132 解析解析解析解析 法 1 因为 甲乙 所以 甲乙乙乙乙 1132 1132 12321088 则乙 甲乙 108832 1288 1088 1000 法 2 将余数先去掉变成整除性问题 利用倍数关系来做 从中减掉以后 就应当1088321056 是乙数的倍 所以得到乙数 甲数 11 1 10561288 1088881000 巩固巩固巩固巩固 一个两位数除一个两位数除 310 余数是 余数是 37 求这样的两位数 求这样的两位数 解析解析解析解析 本题为余数问题的基础题型 需要学生明白一个重要知识点 就是把余数问题 即 不整除问 题 转化为整除问题 方法为用被除数减去余数 即得到一个除数的倍数 或者是用被除数加 上一个 除数与余数的差 也可以得到一个除数的倍数 本题中 310 37 273 说明 273 是所求余数的倍数 而 273 3 7 13 所求的两位数约数还要满 足比 37 大 符合条件的有 39 91 例例 2 年全国小学数学奥林匹克试题年全国小学数学奥林匹克试题 有两个自然数相除 商是有两个自然数相除 商是 余数是 余数是 已知被除数 已知被除数 20031713 除数 商与余数之和为除数 商与余数之和为 则被除数是多少 则被除数是多少 2113 解析解析解析解析 被除数 除数 商 余数 被除数 除数 17 13 2113 所以被除数 除数 2083 由于被除数是 除数的 17 倍还多 13 则由 和倍问题 可得 除数 2083 13 17 1 115 所以被除数 2083 115 1968 巩固巩固巩固巩固 用一个自然数去除另一个自然数 商为用一个自然数去除另一个自然数 商为 40 余数是 余数是 16 被除数 除数 商 余数的和是被除数 除数 商 余数的和是 933 求 求 这这 2 个自然数各是多少 个自然数各是多少 解析解析解析解析 本题为带余除法定义式的基本题型 根据题意设两个自然数分别为 x y 可以得到 解方程组得 即这两个自然数分别是 856 21 4016 40 16933 xy xy 856 21 x y 例 3 2000 2000 年年 祖冲之杯祖冲之杯 小学数学邀请赛试题小学数学邀请赛试题 三个不同的自然数的和为三个不同的自然数的和为 20012001 它们分别除以 它们分别除以 19 23 3119 23 31 所得的商相同 所得的余数也相同 这三个数是所得的商相同 所得的余数也相同 这三个数是 解析解析解析解析 设所得的商为 除数为 由 ab 19 23 31 2001ababab 7332001ab 19b 可求得 所以 这三个数分别是 27a 10b 19523ab 23631ab 31847ab 巩固巩固巩固巩固 2004 年福州市年福州市 迎春杯迎春杯 小学数学竞赛试题小学数学竞赛试题 一个自然数 除以一个自然数 除以 11 时所得到的商和余数是相等时所得到的商和余数是相等 的 除以的 除以 9 时所得到的商是余数的时所得到的商是余数的 3 倍 这个自然数是倍 这个自然数是 解析解析解析解析 设这个自然数除以 11 余 除以 9 余 则有 即a 011 a b 09 b 1193aabb 只有 所以这个自然数为 37ab 7a 3b 84712 例 4 1997 1997 年我爱数学少年数学夏令营试题年我爱数学少年数学夏令营试题 有有 4848 本书分给两组小朋友 已知第二组比第一组多本书分给两组小朋友 已知第二组比第一组多 5 5 人 如果把书全部分给第一组 那么每人人 如果把书全部分给第一组 那么每人 4 4 本 有剩余 每人本 有剩余 每人 5 5 本 书不够 如果把书全分给本 书不够 如果把书全分给 第二组 那么每人第二组 那么每人 3 3 本 有剩余 每人本 有剩余 每人 4 4 本 书不够 问 第二组有多少人本 书不够 问 第二组有多少人 解析解析解析解析 由 知 一组是 10 或 11 人 同理可知 知 二组48412 4859 6 48316 48412 是 13 14 或 15 人 因为二组比一组多 5 人 所以二组只能是 15 人 一组 10 人 巩固巩固巩固巩固 一个两位数除以一个两位数除以 13 的商是的商是 6 除以 除以 11 所得的余数是所得的余数是 6 求这个两位数 求这个两位数 解析解析解析解析 因为一个两位数除以 13 的商是 6 所以这个两位数一定大于 并且小于13 678 又因为这个两位数除以 11 余 6 而 78 除以 11 余 1 这个两位数13 61 91 为 78583 模块二 三大余数定理的应用 例 5 有一个大于有一个大于 1 1 的整数 除的整数 除所得的余数相同 求这个数所得的余数相同 求这个数 45 59 101 解析解析 这个题没有告诉我们 这三个数除以这个数的余数分别是多少 但是由于所得的余数相同 根 据同余定理 我们可以得到 这个数一定能整除这三个数中的任意两数的差 也就是说它是任 意两数差的公约数 的约数有 所以这个1014556 594514 56 14 14 141 2 7 14 数可能为 2 7 14 巩固巩固巩固巩固 有一个整数 除有一个整数 除 39 51 14739 51 147 所得的余数都是所得的余数都是 3 3 求这个数 求这个数 解析解析 法 1 12 的约数是 因为余数为 3 要小39336 1473144 36 144 12 1 2 3 4 6 12 于除数 这个数是 4 6 12 法 2 由于所得的余数相同 得到这个数一定能整除这三个数中的任意两数的差 也就是说它是 任意两数差的公约数 所以这个数是 513912 14739108 12 108 12 4 6 12 巩固巩固巩固巩固 在小于在小于 10001000 的自然数中 分别除以的自然数中 分别除以 1818 及及 3333 所得余数相同的数有多少个所得余数相同的数有多少个 余数可以为余数可以为 0 0 解析解析 我们知道 18 33 的最小公倍数为 18 33 198 所以每 198 个数一次 1 198 之间只有 1 2 3 17 198 余 O 这 18 个数除以 18 及 33 所得的余数相同 而 999 198 5 9 所以共有 5 18 9 99 个这样的数 巩固巩固巩固巩固 2008 2008 年仁华考题年仁华考题 一个三位数除以一个三位数除以 1717 和和 1919 都有余数 并且除以都有余数 并且除以 1717 后所得的商与余数的和等于后所得的商与余数的和等于 它除以它除以 1919 后所得到的商与余数的和 那么这样的三位数中最大数是多少 最小数是多少 后所得到的商与余数的和 那么这样的三位数中最大数是多少 最小数是多少 解析解析 设这个三位数为 它除以 17 和 19 的商分别为和 余数分别为和 则sabmn 1719sambn 根据题意可知 所以 即 得 所以是 9ambn samsbn 1618ab 89ab a 的倍数 是 8 的倍数 此时 由知 bambn 81 99 nmabaaa 由于 为三位数 最小为 100 最大为 999 所以 而 s10017999am 116m 所以 得到 而是 9 的倍数 所以17117999aam 100171716ama 558a a 最小为 9 最大为 54 a 当时 而 所以 故此时 最大为 54a 1 6 9 nma 18n 12m s175412930 当时 由于 所以此时 最小为 9a 1 1 9 nma 1m s1791154 所以这样的三位数中最大的是 930 最小的是 154 例 6 两位自然数两位自然数与与除以除以 7 7 都余都余 1 1 并且 并且 求 求 abbaab abba 解析解析 能被 7 整除 即能被 7 整除 所以只能有 那么abba 10 10 9abbaab 7ab 可能为 92 和 81 验算可得当时 满足题目要求 ab92ab 29 ba 92292668abba 巩固巩固巩固巩固 学校新买来学校新买来 118118 个乒乓球 个乒乓球 6767 个乒乓球拍和个乒乓球拍和 3333 个乒乓球网 如果将这三种物品平分给每个班级 个乒乓球网 如果将这三种物品平分给每个班级 那么这三种物品剩下的数量相同 请问学校共有多少个班 那么这三种物品剩下的数量相同 请问学校共有多少个班 解析解析 所求班级数是除以余数相同的数 那么可知该数应该为和118 67 331186751 673334 的公约数 所求答案为 17 巩固巩固巩固巩固 2000 2000 年全国小学数学奥林匹克试题年全国小学数学奥林匹克试题 在除在除 1351113511 1390313903 及及 1458914589 时能剩下相同余数的最大整数时能剩下相同余数的最大整数 是是 解析解析 因为 3921351113903 6861390314589 由于 13511 13903 14589 要被同一个数除时 余数相同 那么 它们两两之差必能被同一个 数整除 所以所求的最大整数是 98 98 686 392 例 7 2003 2003 年南京市少年数学智力冬令营试题年南京市少年数学智力冬令营试题 与与的和除以的和除以 7 7 的余数是的余数是 2003 2 2 2003 解析解析 找规律 用 7 除 2 的余数分别是 2 4 1 2 4 1 2 4 1 2 2 2 3 2 4 2 5 2 6 2 的个数是 3 的倍数时 用 7 除的余数为 1 2 的个数是 3 的倍数多 1 时 用 7 除的余数为 2 2 的个数是 3 的倍数多 2 时 用 7 除的余数为 4 因为 所以除以 7 余 4 又两 20033 667 2 22 2003 2 个数的积除以 7 的余数 与两个数分别除以 7 所得余数的积相同 而 2003 除以 7 余 1 所以 除以 7 余 1 故与的和除以 7 的余数是 2 2003 2003 2 2 2003415 巩固巩固巩固巩固 2004 2004 年南京市少年数学智力冬令营试题年南京市少年数学智力冬令营试题 在在 19951995 19981998 20002000 20012001 20032003 中 若其中几个数中 若其中几个数 的和被的和被 9 9 除余除余 7 7 则将这几个数归为一组 这样的数组共有 则将这几个数归为一组 这样的数组共有 组 组 解析解析 1995 1998 2000 2001 2003 除以 9 的余数依次是 6 0 2 3 5 因为 252507 25360253679 所以这样的数组共有下面 4 个 2003 2000 2003 2000 1998 1995 2001 2003 2000 1995 2001 2003 2000 1998 例 8 2005 2005 年全国小学数学奥林匹克试题年全国小学数学奥林匹克试题 有一个整数 用它去除有一个整数 用它去除 7070 110110 160160 所得到的所得到的 3 3 个余数个余数 之和是之和是 5050 那么这个整数是 那么这个整数是 解析解析 除数应当是 290 的大于 17 小于 70 的约数 只可能 70110160 50290 50316 2 是 29 和 58 所以除数不是 58 110581 52 5052 所以除数是70292 12 110293 23 160295 15 50152312 29 巩固巩固巩固巩固 2002 2002 年全国小学数学奥林匹克试题年全国小学数学奥林匹克试题 用自然数用自然数 n n 去除去除 6363 9191 129129 得到的三个余数之和为得到的三个余数之和为 2525 那么 那么 n n 解析解析 n 能整除 因为 所以 n 是 258 大于 8 的约数 显然 n258251299163 2538 1 不 能大于 63 符合条件的只有 43 巩固巩固巩固巩固 号码分别为号码分别为 101 126 173 193101 126 173 193 的的 4 4 个运动员进行乒乓球比赛个运动员进行乒乓球比赛 规定每两人比赛的盘数是他们号码规定每两人比赛的盘数是他们号码 的和被的和被 3 3 除所得的余数除所得的余数 那么打球盘数最多的运动员打了多少盘那么打球盘数最多的运动员打了多少盘 解析解析 本题可以体现出加法余数定理的巧用 计算 101 126 173 193 除以 3 的余数分别为 2 0 2 1 那么任意两名运动员的比赛盘数只需要用 2 0 2 1 两两相加除以 3 即可 显然 126 运动员打 5 盘是最多的 例 9 2002 2002 年年 小学生数学报小学生数学报 数学邀请赛试题数学邀请赛试题 六名小学生分别带着六名小学生分别带着 1414 元 元 1717 元 元 1818 元 元 2121 元 元 2626 元 元 3737 元钱 一起到新华书店购买元钱 一起到新华书店购买 成语大词典成语大词典 一看定价才发现有 一看定价才发现有 5 5 个人带的钱不够 个人带的钱不够 但是其中甲 乙 丙但是其中甲 乙 丙 3 3 人的钱凑在一起恰好可买人的钱凑在一起恰好可买 2 2 本 丁 戊本 丁 戊 2 2 人的钱凑在一起恰好可买人的钱凑在一起恰好可买 1 1 本 这种本 这种 成语大词典成语大词典 的定价是的定价是 元 元 解析解析 六名小学生共带钱 133 元 133 除以 3 余 1 因为甲 乙 丙 丁 戊的钱恰好能买 3 本 所以 他们五人带的钱数是 3 的倍数 另一人带的钱除以 3 余 1 易知 这个钱数只能是 37 元 所以 每本 成语大词典 的定价是 元 1417182126 332 巩固巩固巩固巩固 2000 2000 年全国小学数学奥林匹克试题年全国小学数学奥林匹克试题 商店里有六箱货物 分别重商店里有六箱货物 分别重 1515 1616 1818 1919 2020 3131 千克 千克 两个顾客买走了其中的五箱 已知一个顾客买的货物重量是另一个顾客的两个顾客买走了其中的五箱 已知一个顾客买的货物重量是另一个顾客的 2 2 倍 那么商店剩下倍 那么商店剩下 的一箱货物重量是的一箱货物重量是 千克 千克 解析解析 两个顾客买的货物重量是 的倍数 3 剩下的一箱货物重量除以 3 应当余 2 只能 151618192031 12 119339 2 是 20千克 例 10 求求的余数 的余数 2461 135604711 解析解析 因为 根据同余定理 三 2461 11223 8 135 1112 3 604711549 8 的余数等于的余数 而 2461 135604711 8 3 8 11 8 3 8192 所以的余数为 5 1921117 5 2461 135604711 巩固巩固巩固巩固 华罗庚金杯赛模拟试题华罗庚金杯赛模拟试题 求求除以除以 1717 的余数 的余数 478296351 解析解析 先求出乘积再求余数 计算量较大 可先分别计算出各因数除以 17 的余数 再求余数之积除 以 17 的余数 除以 17 的余数分别为 2 7 和 11 478 296 351 27 11 179 1 巩固巩固巩固巩固 求求的最后两位数 的最后两位数 1997 3 解析解析 即考虑除以 100 的余数 由于 由于除以 25 余 2 所以除以 25 余 8 1997 3100425 3 327 9 3 除以 25 余 24 那么除以 25 余 1 又因为除以 4 余 1 则除以 4 余 1 即能被 10 3 20 3 2 3 20 3 20 31 4 和 25 整除 而 4 与 25 互质 所以能被 100 整除 即除以 100 余 1 由于 20 31 20 3 所以除以 100 的余数即等于除以 100 的余数 而除以 1001997209917 1997 3 17 3 6 3729 余 29 除以 100 余 43 所以除以 100 的余数等于除以 5 3243 17625 3 3 3 17 3292943 100 的余数 而除以 100 余 63 所以除以 100 余 63 即的最后两位29294336163 1997 3 1997 3 数为 63 巩固巩固巩固巩固 除以除以 1313 所得余数是所得余数是 2 2000 2222 个 解析解析 我们发现整除 13 2000 6 余 2 所以答案为 22 13 余 9 巩固巩固巩固巩固 求求除以除以 7 7 的余数 的余数 89 143 解析解析 法一 由于 143 被 7 除余 3 1433 mod7 所以 被 7 除所得余数与被 7 除所得余数相等 8989 1433mod7 89 143 89 3 而 729 除以 7 的余数为 1 6 3729 7291 mod7 所以 8966655 14 3333335 mod7 个 故除以 7 的余数为 5 89 143 法二 计算被 7 除所得的余数可以用找规律的方法 规律如下表 89 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 mod73264513 于是余数以 6 为周期变化 所以 895 335 mod7 巩固巩固巩固巩固 20072007 年实验中学考题 年实验中学考题 除以除以 7 7 的余数是多少 的余数是多少 2222 12320012002 解析解析 由于 而 1001 是 7 的倍 22222 200220034005 123200120021001 2003 1335 6 数 所以这个乘积也是 7 的倍数 故除以 7 的余数是 0 22222 12320012002 巩固巩固巩固巩固 被被除所得的余数是多少 除所得的余数是多少 3031 3130 13 解析解析 31 被 13 除所得的余数为 5 当 n 取 1 2 3 时被 13 除所得余数分别是 5n 5 12 8 1 5 12 8 1以 4 为周期循环出现 所以被 13 除的余数与被 13 除的余数 30 5 2 5 相同 余 12 则除以 13 的余数为 12 30 31 30 被 13 除所得的余数是 4 当 n 取 1 2 3 时 被 13 除所得的余数分别是 4n 4 3 12 9 10 1 4 3 12 9 10 以 6 为周期循环出现 所以被 13 除所得的余 31 4 数等于被 13 除所得的余数 即 4 故除以 13 的余数为 4 1 4 31 30 所以被 13 除所得的余数是 3031 3130 124133 巩固巩固巩固巩固 2008 2008 年奥数网杯年奥数网杯 已知已知 问 问 除以除以 1313 所得的余数是多少 所得的余数是多少 20082008 200820082008a 个 a 解析解析 2008 除以 13 余 6 10000 除以 13 余 3 注意到 200820082008 100002008 20082008200820082008 100002008 2008200820082008200820082008 100002008 根据这样的递推规律求出余数的变化规律 除以 13 余 8 除以 13 余 即 8 是 13 的倍数 6361311 11 36390 而除以 3 余 1 所以除以 13 的余数与除以 13 的余数相同 为 6 2008 20082008 200820082008a 个 2008 巩固巩固巩固巩固 除以除以 4141 的余数是多少 的余数是多少 19967 77777 个 解析解析 找规律 7417 774136 7774139 77774128 所以 77777 是 41 的倍数 而 所以可以77777410 199653991 19967 77777 个 分成 399 段 77777 和 1 个 7 组成 那么它除以 41 的余数为 7 巩固巩固巩固巩固 除以除以 1010 所得的余数为多少 所得的余数为多少 12342005 12342005 解析解析 求结果除以 10 的余数即求其个位数字 从 1 到 2005 这 2005 个数的个位数字是 10 个一循环的 而对一个数的幂方的个位数 我们知道它总是 4 个一循环的 因此把所有加数的个位数按每 20 个 20 是 4 和 10 的最小公倍数 一组 则不同组中对应的个位数字应该是一样的 首先计算的个位数字 123420 123420 为的个位数字 为 4 1476563690163656749094 由于 2005 个加数共可分成 100 组另 5 个数 100 组的个位数字和是的个位数即 0 4 100400 另外 5 个数为 它们和的个位数字是 2001 2001 2002 2002 2003 2003 2004 2004 2005 2005 的个位数 3 所以原式的个位数字是 3 即除以 10 的余数是 3 1476523 例 11 求所有的质数求所有的质数 P P 使得 使得与与也是质数 也是质数 2 41p 2 61p 解析解析 如果 则 都是质数 所以 5 符合题意 如果 P 不等于 5 那么5p 2 41101p 2 61151p P 除以 5 的余数为 1 2 3 或者 4 除以 5 的余数即等于 或者除以 5 的余数 2 p 2 1 2 2 2 3 2 4 即 1 4 9 或者 16 除以 5 的余数 只有 1 和 4 两种情况 如果除以 5 的余数为 1 那么 2 p 除以 5 的余数等于除以 5 的余数 为 0 即此时被 5 整除 而 2 41p 4 1 15 2 41p 大于 5 所以此时不是质数 如果除以 5 的余数为 4 同理可知不是质 2 41p 2 41p 2 p 2 61p 数 所以 P 不等于 5 与至少有一个不是质数 所以只有满足条件 2 41p 2 61p 5p 巩固巩固巩固巩固 在图表的第二行中 恰好填上在图表的第二行中 恰好填上这十个数 使得每一竖列上下两个因数的乘积除以这十个数 使得每一竖列上下两个因数的乘积除以 1111 所所8998 得的余数都是得的余数都是 3 3 解析解析 因为两个数的乘积除以 11 的余数 等于 两个数分别除以 11 的余数之积 因此原题中的8998 可以改换为 这样上下两数的乘积除以 11 余 3 就容易计算了 我们得到下面的结果 110 进而得到本题的答案是 因因 数数 89909192939495969798 因因 数数 91958997939490989296 巩固巩固巩固巩固 2000 2000 年年 华杯赛华杯赛 试题试题 3 3 个三位数乘积的算式个三位数乘积的算式 其中其中 234235286abcbcacab abc 在校对时 发现右边的积的数字顺序出现错误 但是知道最后一位在校对时 发现右边的积的数字顺序出现错误 但是知道最后一位 6 6 是正确的 问原式中的是正确的 问原式中的 是多少 是多少 abc 解析解析 由于 2342352862342352868 mod9 3 mod9 abcbcacababc 于是 从而 用代入上式检验 3 8 mod9 abc 0 1 2 8 mod9 abc 1 对进行讨论 2 5 8 mod9 abc a 如果 那么 2 又的个位数字是 6 所以的个位数字为9a 2 5 8 mod9 bc cab bc 4 可能为 其中只有符合 2 经检验只有bc 4 1 72 8 3 64 4 1 8 3 b c 符合题意 983 839398328245326 因数因数89909192939495969798 因数因数 因数因数89909192939495969798 因数因数37195621048 如果 那么 3 又的个位数字为 2 或 7 则可能为 8a 3 6 0 mod9 bc bc bc 2 1 其中只有符合 3 经检验 不合题意 43 62 76 7 1 2 1 b c 821abc 如果 那么 4 则可能为 其中没有符合 4 的7a 4 7 1 mod9 bc bc 42 63 b c 如果 那么 因此6a 5b 4c 700600500210000000222334586abcbcacab 这时不可能符合题意 综上所述 是本题唯一的解 abc983abc 例 12 一个大于一个大于 1 1 的数去除的数去除 290290 235235 200200 时 得余数分别为时 得余数分别为 则这个自然数是多 则这个自然数是多a2a 5a 少 少 解析解析 根据题意可知 这个自然数去除 290 233 195 时 得到相同的余数 都为 a 既然余数相同 我们可以利用余数定理 可知其中任意两数的差除以这个数肯定余 0 那么这个 自然数是的约数 又是的约数 因此就是 57 和 38 的公约数 因为29023357 233 19538 57 和 38 的公约数只有 19 和 1 而这个数大于 1 所以这个自然数是 19 巩固巩固巩固巩固 一个大于一个大于 1010 的自然数去除的自然数去除 9090 164164 后所得的两个余数的和等于这个自然数去除后所得的两个余数的和等于这个自然数去除 220220 后所得的余后所得的余 数 则这个自然数是多少 数 则这个自然数是多少 解析解析 这个自然数去除 90 164 后所得的两个余数的和等于这个自然数去除后所得的余90164254 数 所以 254 和 220 除以这个自然数后所得的余数相同 因此这个自然数是的约25422034 数 又大于 10 这个自然数只能是 17 或者是 34 如果这个数是 34 那么它去除 90 164 220 后所得的余数分别是 22 28 16 不符合题目条件 如果这个数是 17 那么他去除 90 164 220 后所得的余数分别是 5 11 16 符合题目条件 所以这个自然数是 17 例 13 甲 乙 丙三数分别为甲 乙 丙三数分别为 603603 939939 393393 某数 某数除甲数所得余数是除甲数所得余数是除乙数所得余数的除乙数所得余数的 2 2 倍 倍 AA 除乙数所得余数是除乙数所得余数是除丙数所得余数的除丙数所得余数的 2 2 倍 求倍 求等于多少 等于多少 AAA 解析解析 根据题意 这三个数除以都有余数 则可以用带余除法的形式将它们表示出来 A 11 603AKr 22 939AKr 33 393AKr 由于 要消去余数 我们只能先把余数处理成相同的 再两数相减 12 2rr 23 2rr 1 r 2 r 3 r 这样我们先把第二个式子乘以 2 使得被除数和余数都扩大 2 倍 同理 第三个式子乘以 4 于是我们可以得到下面的式子 11 603AKr 22 939222AKr 这样余数就处理成相同的 最后两两相减消去余数 意味着能被整 33 393424AKr A 除 93926031275 3934603969 1275 969513 17 51 的约数有 1 3 17 51 其中 1 3 显然不满足 检验 17 和 51 可知 17 满足 所以等于A 17 巩固巩固巩固巩固 一个自然数除一个自然数除 429429 791791 500500 所得的余数分别是所得的余数分别是 求这个自然数和 求这个自然数和的值的值 5a 2aaa 解析解析 将这些数转化成被该自然数除后余数为的数 这2a 42952848 79150021000 样这些数被这个自然数除所得的余数都是 故同余 2a 将这三个数相减 得到 所求的自然数一定是和的公约84879157 1000848152 57152 数 而 所以这个自然数是的约数 显然 1 是不符合条件的 那么只能是 19 经 57 15219 19 过验证 当这个自然数是时 除 所得的余数分别为 时成19429791500111266a 立 所以这个自然数是 196a 模块三 余数综合应用 例 14 著名的裴波那契数列是这样的 著名的裴波那契数列是这样的 1 1 1 1 2 2 3 3 5 5 8 8 1313 21 21 这串数列当中第这串数列当中第 20082008 个数除个数除 以以 3 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 巩固巩固巩固巩固 20092009 年走美初赛六年级 有一串数 年走美初赛六年级 有一串数 1 1 1 1 2 2 3 3 5 5 8 8 从第三个数起 每个数都是 从第三个数起 每个数都是 前两个数之和 在这串数的前前两个数之和 在这串数的前 20092009 个数中 有几个是个数中 有几个是 5 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 个数中 有 401 个是 5 的倍数 200954014 例 15 圣彼得堡数学奥林匹克试题圣彼得堡数学奥林匹克试题 托玛想了一个正整数 并且求出了它分别除以托玛想了一个正整数 并且求出了它分别除以 3 3 6 6 和和 9 9 的余的余 数 现知这三余数的和是数 现知这三余数的和是 1515 试求该数除以 试求该数除以 1818 的余数 的余数 解析解析 除以 3 6 和 9 的余数分别不超过 2 5 8 所以这三个余数的和永远不超过 15852 既然它们的和等于 15 所以这三个余数分别就是 2 5 8 所以该数加 1 后能被 3 6 9 整除 而 设该数为 则 即 为非零自然数 所以它除 3 6 9 18 a181am 18 1 17am m 以 18 的余数只能为 17 巩固巩固巩固巩固 2005 2005 年香港圣公会小学数学奥林匹克试题年香港圣公会小学数学奥林匹克试题 一个家庭 有父 母 兄 妹四人 他们任意三人一个家庭 有父 母 兄 妹四人 他们任意三人 的岁数之和都是的岁数之和都是 3 3 的整数倍 每人的岁数都是一个质数 四人岁数之和是的整数倍 每人的岁数都是一个质数 四人岁数之和是 100100 父亲岁数最大 父亲岁数最大 问 母亲是多少岁问 母亲是多少岁 解析解析 从任意三人岁数之和是 3 的倍数 100 除以 3 余 1 就知四个岁数都是型的数 又是质31k 数 只有 7 13 19 31 37 43 就容易看出 父 43 岁 母 37 岁 兄 13 岁 妹 7 岁 例 16 华杯赛试题华杯赛试题 如图 在一个圆圈上有几十个孔如图 在一个圆圈上有几十个孔 不到不到 100100 个个 小明像玩跳 小明像玩跳 棋那样 从棋那样 从孔出发沿着逆时针方向 每隔几孔跳一步 希望一圈以后能孔出发沿着逆时针方向 每隔几孔跳一步 希望一圈以后能 A 跳回到跳回到 A A 孔 他先试着每隔孔 他先试着每隔 2 2 孔跳一步 结果只能跳到孔跳一步 结果只能跳到 B B 孔 他又试着每孔 他又试着每 隔隔 4 4 孔跳一步 也只能跳到孔跳一步 也只能跳到 B B 孔 最后他每隔孔 最后他每隔 6 6 孔跳一步 正好跳回到孔跳一步 正好跳回到 A A 孔 你知道这个圆圈上共有多少个孔吗孔 你知道这个圆圈上共有多少个孔吗 解析解析 设想圆圈上的孔已按下面方式编了号 A 孔编号为 1 然后沿逆时针方向顺次编号 为 2 3 4 B 孔的编号就是圆圈上的孔数 我们先看每隔 2 孔跳一步时 小明跳在哪些孔上 很容易看出应在 1 4 7 10 上 也就是 说 小明跳到的孔上的编号是 3 的倍数加 1 按题意 小明最后跳到 B 孔 因此总孔数是 3 的倍 数加 1 同样道理 每隔 4 孔跳一步最后跳到 B 孔 就意味着总孔数是 5 的倍数加 1 而每隔 6 孔跳一步 最后跳回到 A 孔 就意味着总孔数是 7 的倍数 如果将孔数减 1 那么得数既是 3 的倍数也是 5 的倍数 因而是 15 的倍数 这个 15 的倍数加上 1 就等于孔数 设孔数为 则 为非零自然数 而且能被 7 整除 注意 15 被a151am ma 7 除余 1 所以被 7 除余 6 15 的 6 倍加 1 正好被 7 整除 我们还可以看出 15 的其他 小156 于的 7 倍数加 1 都不能被 7 整除 而已经大于 100 7 以上的倍数都不必考虑 因此 157105 总孔数只能是 156191 巩固巩固巩固巩固 1997 1997 年全国小学数学奥林匹克试题年全国小学数学奥林匹克试题 将将依次写到第依次写到第 19971997 个数字 组成个数字 组成12345678910111213 一个一个 19971997 位数 那么此数除以位数 那么此数除以 9 9 的余数是的余数是 解析解析 本题第一步是要求出第 1997 个数字是什么 再对数字求和 共有 9 个数字 共有 90 个两位数 共有数字 个 共 90019 1099 902180 100999 B A 个三位数 共有数字 个 所以数连续写 不会写到 999 从 100 开始是 3 位数 90032700 每三个数字表示一个数 即有 602 个三位数 第 603 个三位数只 19979180 3602 2 写了它的百位和十位 从 100 开始的第 602 个三位数是 701 第 603 个三位数是 9 其中 2 未写 出来 因为连续 9 个自然数之和能被 9 整除 所以排列起来的 9 个自然数也能被 9 整除 702 个 数能分成的组数是 组 依次排列后 它仍然能被 9 整除 但 702 中 2 未写出来 702978 所以余数为 9 27 例 17 设设是质数 证明 是质数 证明 被被除所得的余数各不相同 除所得的余数各不相同 21n 2 1 2 2 2 n21n 解析解析 假设有两个数 它们的平方 被除余数相同 那么 由ab1ban 2 a 2 b21n 同余定理得 即 由于是质数 所以 22 0 mod 21 abn 0 mod 21 ab abn 21n 或 由于 均小于且大于 0 可知 0 mod 21 abn 0 mod 21 abn ab ab 21n 与互质 也与互质 即 都不能被整除 产生矛盾 所ab 21n ab 21n ab ab 21n 以假设不成立 原题得证 巩固巩固巩固巩固 试求不大于试求不大于 100100 且使 且使能被能被 1111 整除的所有自然数整除的所有自然数 n n 的和 的和