同余法解题(2)

1、五年级奥数培训资料第六讲同余法解题一、 同余这个概念最初就是由德国数学家高斯发明的。同余的定义就是这样的 : 两个整数 ,a,b,如果她们同时除以一个自然数 m,所得的余数相同 ,则称 a,b 对于模 m 同余。记作 a b(mod、m)。读作 :a 同余于 b 模 m。 同余的性质也比较多 ,主要有以下一些 :1、对于同一个除数 ,两个数的乘积与它们余数的乘积同余。例如 201 95 的乘积对于除数 7,与 2017 的余数 5 与 957 的余数 4 的乘积 20 对于 7 同余。2、对于同一个除数 ,如果有两个整数同余 ,那么它们的差就一定能被这个除数整除。例如 519 与 399 对于

2、一个除数同余 ,那么这个除数一定就是 519 与 399 的差的因数 ,即 519 与 399 的差一 定能被这个除数整除。3、对于同一个除数 ,如果两个数同余 ,那么她们的乘方仍然同余。例如 20 与 29 对于一个除数同余 ,那么 20 的任何次方都与 29 的相同次方对于这个除数同余 ,当然余数大小随次方变化。4.对于同一个除数 ,若三个数 a b(mod m),b c(mod 那m),么 a,b,c三个数对于除数 m 都同余 (传递性 )例如 60 与 76 同余于模 8,76 与 204 同余于模 8,那么 60,76,204都同余于模 8。5、 对于同一个除数 ,若四个数 a b(

3、mod m),c d(mod那m),么 a c c d(mod 可m),(加减性 )6、对于同一个除数 , 若四个数 a b(mod m),c d(mod那m),么 ac cd(mod m),(可乘性 )二、中国剩余定理解法一个数被 3 除余 1,被 4 除余 2,被 5 除余 4,这个数最小就是几？解法 :求 3 个数 :第一个 :能同时被 3 与 4 整除 ,但除以 5 余 4,即 12X224第二个 :能同时被 4 与 5 整除 ,但除以 3 余 1,即 20X240第三个 :能同时被 3 与 5 整除 ,但除以 4 余 2,即 15x230这 3 个数的最小公倍数为 60,所以满足条件

4、的最小数字为 2440+30-60=3412X22420X24015x230 中 2 的来历。三、解题技巧同余口诀 : “差同减差 ,与同加与 ,余同取余 ,最小公倍 n 倍加 ”这就是同余问题的口诀。1)、差同减差 :用一个数除以几个不同的数,得到的余数 ,与除数的差相同 ,此时反求的这个数 ,可以选除数的最小公倍数 ,减去这个相同的差数 ,称为 : “差同减差 ”。例 : “一个数除以 4余 1,除以 5 余 2,除以 6 余 3”,因为 4-1=5-2=6-3=3,所以取 -3,表示为 60-3 或者 60n-32)、与同加与 :用一个数除以几个不同的数 ,得到的余数 ,与除数的与相同

5、,此时反求的这个数 ,可以选除数的最小公倍数 ,加上这个相同的与数 ,称为 : “与同加与 ”。例 : “一个数除以 4余 3,除以 5 余 2,除以 6 余 1”,因为 4+3=5+2=6+1=7,所以取 +7,表示为 60n+7。3)、余同取余 :用一个数除以几个不同的数,得到的余数相同 ,此时反求的这个数 ,可以选除数的最小公倍数 ,加上这个相同的余数 ,称为 : “余同取余 ”。例 : “一个数除以 4 余 1,除以 5 余 1,除以 6 余 1”,因为余数都就是 1,所以取 +1,表示为 60n+1。4)、最小公倍加 :所选取的数加上除数的最小公倍数的任意整数倍(即上面 1、2、3

6、中的60n)都满足条件 ,称为 : “最小公倍 n 倍加 ”,也称为 : “公倍数作周期 ”。三、例题解评例 1:判定 288 与 214 对于模 37 就是否同余思路点拨 :可直接由定义判断。解 :288-214=74=372 288214(mod 37)例 2、 用 412、133 与 257 除以一个相同的自然数 ,所得的余数相同 ,这个自然数最大就是几？【解析】假设这个自然数就是 a,因为 412、133 与 257 除以 a 所得的余数相同 ,所以 a(412 133),a(412257),a(257133),说明 a 就是以上三个数中任意两数差的约数 ,要求最大就是几 ,就就是求这

7、三个差的最大公约数。 (155,124,279)=31,所以 a 最大就是 31。例 3、 249388234 除以 19,余数就是几？【解析】如果把三个数相乘的积求出来再除以 19,就太麻烦了 ,利用同余思想解决就容易了。因为 2492(mdo19), 388 8(mdo19),234 6(mdo19), 所以 2493882342861(mdo19)此题应用了同余的可乘性,同余的传递性。例 4:求 199259 除以 7 的余数。思路点拨 :可应用性质 2,将 199259 转化为求 1992 除以 7 与 59 除以 7 的余数的乘积 ,使计算简化。解 :19924(mod 7),59

8、3(mod 7)根据性质 5 可得 :1992 5943(mod,余7)数为 127 的余数。答 :1992 59 除以 7 的余数就是 5。例 5:自然数 16520、 14903、14177 除以 m 的余数相同 ,m 的最大值就是多少？思路点拨 :自然数 16520、 14903、14177 除以 m 的余数相同 ,也就就是16520 14903 14177(mod m)根据同余补充定义 ,这三个数同余 ,那么它们的差就能被 m 整除。要求 m 最大就是多少 ,就就是求它们差的最大公约数就是多少。解 :因为 16520-14903=161716520-14177=234314903-14

9、177=726(1617、 2343、 726)=33所以 m 的最大值就是33。评注实际上 ,这三个差数还可以继续两两相减 ,得到 1617-726=891,891-726=165,算出 726 与 165 的最大公约数即可 ,通常其结果与上面相同。例 6:在除 13511,13903,及 14598 时能剩下相同余数的最大整数就是几？思路点拨 :根据同余的性质 ,若几个数被同一个数除 ,余数相同 ,则这几个数中两两相减的差必能被这个数整除。所以这个数应就是这三个数两两相减后所得数的最大公约数。解 :这两个数两两只减的差就是 : 13903-13511=392 14598-13903=686

10、14589-13511=1078因为 (392,686,1078)=98,所以这个数就是98。也可以以上三个差再两两相减 ,得 686-392=294,再 392-294=98 答 :这个最大整数就是 98。例 7:一个三位数除以 9 余 7,除以 5 余 2,除以 4 余 3。这样的三位数共有几个？思路点拨 :由中国剩余定理解法求。解法 :求 3 个数 :第一个 :能同时被 9 与 5 整除 ,但除以 4 余 3,即 45X3135第二个 :能同时被 4 与 5 整除 ,但除以 9 余 7,即 20X8160第三个 :能同时被 9 与 4 整除 ,但除以 5 余 2,即 36x272这 3

11、个数的最小公倍数为 180,所以满足条件的最小数字为 135 160+72-180=18771805=907 100071806=10871000所以符合条件的三位数共有 5 个。分别就是 7180n(n=1,2,4,5)、答 :这样的三位数共有 5 个。例 8、 有一个 1997 位数 ,它的每个数位都就是2,这个数除以13,商的第 100位就是几？最后余数就是几？【解析】这个数除以 13,商就是有规律的。商就是 170940 六个数循环 ,那么,即,我们从左向右数“ 170940的”第 4 个数就就是我们找的那个数 “ 9”,所以商的第 100 位就是 9。余数就是几呢？则解析过程 :本题

12、商共有 1996 位 ,每 6 位循环 ,共有 332 次循环后余 4,所以商的个位数字应就是“170940中”的第 4 个,商应就是 9,个位的余数就对应商为9 时的余数 5。三、练习题1、 求下列算式中的余数。(1)(2)(3)(4)2、 6254 与 37 的积除以 7,余数就是几？3、 如果某数除 482,992,1094都余 74,这个数就是几？4、300、262、 205 被同一个整数除 ,得到相同的余数 ,这个整数就是几？5、一个自然数被 247 除余 63,被 248 除余 63,求这个自然数被26 除的余数。6、一个自然数 N 被 10 除余 9,被 9 除余 8,被 8 除余 7,被 7 除余 6,被 6 除余 5,被 5 除余4,被 4 除余 3,被 3 除余