同余法解题.pdf

《同余法解题.pdf》由会员分享，可在线阅读，更多相关《同余法解题.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、五年级奥数培训资料第六讲同余法解题一、同余这个概念最初是由德国数学家高斯发明的。同余的定义是这样的：两个整数，a,b,如果他们同时除以一个自然数 m，所得的余数相同，则称 a,b 对于模 m同余。记作 ab（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对于同一个除数，若三个数 ab（mod m），bc（mod m），那么 a,b,c 三个数对于除数 m 都同余（传递性）例如 60 和 76 同余于模 8，76 和 204 同余于模 8，那么 60,76,204 都同余于模 8。5.对于同一个除数，若四个数 ab（mod m），cd（mod m），那么 accd（mod m），

3、（可加减性）6.对于同一个除数，若四个数 ab（mod m），cd（mod m），那么 accd（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，所以满足条件的最小数字为 2440+30-60=3412X22420X24015x230 中 2 的来历。三、解题

4、技巧同余口诀：“差同减差，和同加和，余同取余，最小公倍 n 倍加”这是同余问题的口诀。1）、差同减差：用一个数除以几个不同的数，得到的余数，与除数的差相同，此时反求的这个数，可以选除数的最小公倍数，减去这个相同的差数，称为：“差同减差”。例：“一个数除以 4 余 1，除以 5 余 2，除以 6 余 3”，因为 4-1=5-2=6-3=3，所以取-3，表示为 60-3 或者 60n-32）、和同加和：用一个数除以几个不同的数，得到的余数，与除数的和相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的和数，称为：“和同加和”。例：“一个数除以 4 余 3，除以 5 余 2，除以 6 余

5、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 中的 60n）都满足条件，称为：“最小公倍 n 倍加”，也称为：“公倍数作周期”。三、例题解评例 1：判定 288 和 214 对于模 37 是否同余思路点拨：可直接由定义判断。解：288-2

6、14=74=372288214（mod 37）例 2、用 412、133 和 257 除以一个相同的自然数，所得的余数相同，这个自然数最大是几【解析】假设这个自然数是 a，因为 412、133 和 257 除以 a 所得的余数相同，所以 a(412133),a(412257),a(257133),说明 a 是以上三个数中任意两数差的约数，要求最大是几，就是求这三个差的最大公约数。(155,124,279)=31,所以 a 最大是 31。例 3、249388234 除以 19，余数是几【解析】如果把三个数相乘的积求出来再除以 19，就太麻烦了，利用同余思想解决就容易了。因为 2492（mdo19

7、）,3888（mdo19）,2346（mdo19）,所以 2493882342861（mdo19）此题应用了同余的可乘性，同余的传递性。例 4：求 199259 除以 7 的余数。思路点拨：可应用性质 2，将 199259 转化为求 1992 除以 7 和 59 除以 7 的余数的乘积，使计算简化。解：19924（mod 7），593（mod 7）根据性质 5 可得：19925943（mod 7），余数为 127 的余数。答：199259 除以 7 的余数是 5。例 5：自然数 16520、14903、14177 除以 m 的余数相同，m 的最大值是多少思路点拨：自然数 16520、14903

8、、14177 除以 m 的余数相同，也就是165201490314177（mod m）根据同余补充定义，这三个数同余，那么它们的差就能被m 整除。要求m 最大是多少，就是求它们差的最大公约数是多少。解：因为 16520-14903=161716520-14177=234314903-14177=726（1617、2343、726）=33所以 m 的最大值是 33。评注实际上，这三个差数还可以继续两两相减，得到 1617-726=891,891-726=165，算出 726 和 165 的最大公约数即可，通常其结果与上面相同。例 6：在除 13511，13903，及 14598 时能剩下相同余数

9、的最大整数是几思路点拨：根据同余的性质，若几个数被同一个数除，余数相同，则这几个数中两两相减的差必能被这个数整除。所以这个数应是这三个数两两相减后所得数的最大公约数。解：这两个数两两只减的差是：13903-13511=39214598-13903=68614589-13511=1078因为（392，686，1078）=98，所以这个数是 98。也可以以上三个差再两两相减，得 686-392=294，再 392-294=98答：这个最大整数是 98。例 7：一个三位数除以 9 余 7，除以 5 余 2，除以 4 余 3。这样的三位数共有几个思路点拨：由中国剩余定理解法求。解法：求 3 个数：第一

10、个：能同时被 9 和 5 整除，但除以 4 余 3，即 45X3135第二个：能同时被 4 和 5 整除，但除以 9 余 7，即 20X8160第三个：能同时被 9 和 4 整除，但除以 5 余 2，即 36x272这 3 个数的最小公倍数为 180，所以满足条件的最小数字为 135160+72-180=18771805=907 1000?71806=10871000所以符合条件的三位数共有 5 个。分别是 7180n（n=1,2,4,5）.答：这样的三位数共有 5 个。例 8、有一个 1997 位数，它的每个数位都是 2，位是几最后余数是几这个数除以 13，商的第 100【解析】这个数除以

11、13，商是有规律的。，即，我们从左向右数商是 170940 六个数循环，那么“170940”的第 4 个数就是我们找的那个数“9”，所以商的第 100 位是 9。余数是几呢则解析过程：本题商共有 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 被同一个整数除，得到相同的余数，这个整数是几

12、5、一个自然数被 247 除余 63，被 248 除余 63，求这个自然数被 26 除的余数。6、一个自然数 N 被 10 除余 9，被 9 除余 8，被 8 除余 7，被 7 除余 6，被 6 除余 5，被5 除余 4，被 4 除余 3，被 3 除余 2，被 2 除余 1，求 N 的最小值。7、两个数除以 11 分别余 9 和 10，这两个数的和除以 11 余几8、甲、乙、丙三个数之和是 100，甲数除以乙数，或丙数除以甲数，得数都商 5 余 1，乙数是多少9、求下列各式的余数。（1）21236（2）48548（3）求 20 的 200 次方 除以 13 的余数。（4）求 80 的 1000 次方 除以 12 的余数。