小学奥数竞赛专题之同余问题

小学奥数竞赛专题之同余问题[专题介绍]：同余问题生活中我会经常遇到与余数有关的问题，比如：某年级有将近400名学生。有一次演出节目排队时出现：如果每8人站成一列则多余1人；如果改为每9人站成一列则仍多余1人；结果发现现成每10人结成一列，结果还是多余1人；聪名的你知道该年级共有学生多少名吗？假设有一名学生不参加演出，则结果一定是不管每列站8人或9人或10人都将刚好站齐。因此此时学生人数应是8、9、10公倍数，而8、9、10的最小公倍数是360，因此可知该年级共有361人。研究与余数有关的问题，能帮助我们解决很多较为复杂的问题。[分析]1、两个整数a和b，除以一个大于1的自然数m所得余数相同，就称a和b对于模m同余或称a和b在模m下同余，即a≡b（modm）2、同余的重要性质及举例。〈1〉a≡a（modm）（a为任意自然）〈2〉若a≡b（modm），则b≡a（modm）〈3〉若a≡b（modm），b≡c（modm）则a≡c（modm）〈4〉若a≡b（modm），则ac≡bc（modm）〈5〉若a≡b（modm），c≡d（modm），则ac=bd（modm）〈6〉若a≡b（modm）则an≡bm（modm）其中性质〈3〉常被称为同余的可传递性，性质〈4〉、〈5〉常被称为同余的可乘性，性质〈6〉常被称为同余的可开方性注意：一般地同余没有可除性，但是：如果：ac=bc（modm）且（c，m）=1则a≡b（modm）3、整数分类：〈1〉用2来将整数分类，分为两类：1，3，5，7，9，……（奇数）0，2，4，6，8，……（偶数）〈2〉用3来将整数分类，分为三类：0，3，6，9，12，……（被3除余数是0）1，4，7，10，13，……（被3除余数是1）2，5，8，11，14，……（被3除余数是2）〈3〉在模6的情况下，可将整数分成六类，分别是：0（mod6）：0，6，12，18，24，……1（mod6）：1，7，13，19，25，……2（mod6）：2，8，14，20，26，……3（mod6）：3，9，15，21，27，……4（mod6）：4，10，16，22，29，……5（mod6）：5，11，17，23，29，……[经典例题]例1：求437×309×1993被7除的余数。思路分析：如果将437×309×1993算出以后，再除以7，从而引得到，即437×309×1993=269120769，此数被7除的余数为1。但是能否寻找更为简变的办法呢？473≡3（mod7）309≡1（mod7）由同余的可乘性知：437×309≡3×1（mod7）≡3（mod7）又因为1993≡5（mod7）所以：437×309×1993≡3×5（mod7）≡15（mod7）≡1（mod7）即：437×309×1993被7除余1。例2：70个数排成一行，除了两头的两个数以外，每个数的三倍恰好等于它两边两个数的和，这一行最左边的几个数是这样的：0，1，3，8，21，……，问这一行数最右边的一个数被6除的余数是几？思路分析：如果将这70个数一一列出，得到第70个数后，再用它去除以6得余数，总是可以的，但计算量太大。即然这70个数中：中间的一个数的3倍是它两边的数的和，那么它们被6除以后的余数是否有类似的规律呢？0，1，3，8，21，55，144，……被6除的余数依次是0，1，3，2，3，1，0，……结果余数有类似的规律，继续观察，可以得到：0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，……可以看出余数前12个数一段，将重复出现。70÷2=5……10，第六段的第十个数为4，这便是原来数中第70个数被6除的余数。思路分析：我们被直接用除法算式，结果如何。例4、分别求满足下列条件的最小自然数：（1）用3除余1，用5除余1，用7除余1。（2）用3除余2，用5除余1，用7除余1。（3）用3除余1，用5除余2，用7除余2。（4）用3除余2，用7除余4，用11除余1。思路分析：（1）该数减去1以后，是3，5和7的最小公倍数105，所以该数的是105+1=106（2）该数减去1以后是5和7的公倍数。因此我们可以以5和7的公倍数中去寻找答案。下面列举一些同时被5除余1，被7除余1的数，即1，36，71，106，141，176，211，246，……从以上数中寻找最小的被3除余2的数。36≡0（mod3），71≡2（mod3），符合条件的最小的数是71。（3）我们首先列举出被5除余2，被7除余2的数，2，37，72，107，142，177，212，247，……从以上数中寻找最小的被3除余1的数。2（mod3），37≡（mod3）、因此符合条件的最小的数是37。（4）我们从被11除余1的数中寻找答案。1，12，23，34，45，56，67，78，89，100，133，144，155，166，177，188，199，210，232，243，……1（mod3）；1（mod7），不符合12≡0（mod3），12≡5（mod7）不符合23≡2（mod3），23≡2（mod7）不符合34≡1（mod3），34≡6（mod7）不符合45≡0（mod3），45≡3（mod7）不符合56≡2（mod3），56≡0（mod7）不符合67≡1（mod3），67≡4（mod7）不符合78≡0（mod3），78≡1（mod7）不符合89≡2（mod3），89≡5（mod7）不符合100≡1（mod3），100≡2（mod7）不符合122≡2（mod3），122≡3（mod7）不符合133≡1（mod3），133≡0（mod7）不符合144≡1（mod3），144≡4（mod7）不符合155≡2（mod3），155≡1（mod7）不符合166≡1（mod3），166≡5（mod7）不符合177≡0（mod3），177≡2（mod7）不符合188≡2（mod3），188≡6（mod7）不符合199≡1（mod3），199≡3（mod7）不符合210≡0（mod3），210≡0（mod7）不符合221≡2（mod3），221≡4（mod7）符合因此符合条件的数是221。例5判断以下计算是否正确（1）42784×3968267=1697598942346（2）42784×3968267=1697598981248思路分析：若直接将右边算出，就可判断41784×3968267=169778335328，可知以上两结果均是错的；但是计算量太大。如果右式和左式相等，则它们除以某一个数余数一定相同。因为求一个数除以9的余数只需要先求这个数数字之和除以9的余数，便是原数除以9的余数。我考虑上式除以9的余数，如果余数不相同，则上式一定不成立。（1）从个位数字可知，右式的个位数字只能是8，而右式个位为6，因此上式不成立。（2）右式和左式的个位数字相同，因而无法断定上式是否成立，但是4+2+7+8+4=25，25≡7（mod9）3+9+6+8+2+6+7=41，41≡5（mod9）42784≡7（mod9）；3968267≡5（mod9）42784×3968267≡35（mod9）≡8（mod9）（1+6+9+7+5+9+8+9+4+2+3+4+8）≡3（mod9）因此（2）式不成立以上是用除9取余数来验证结果是否正确，常被称为弃九法。不过应该注意，用弃九法可发现错误，但用弃九法没找出错误却不能保证原题一定正确。习题1、求16×941×1611被7除的余数。3、判断结果是否正确：（1）5483×9117=49888511（2）1226452÷2683=3344、乘法算式3145×92653=291093995的横线处漏写了一个数字，你能以最快的办法补出吗？5、13511，13903，14589被自然数m除所得余数相同，问m最大值是多少？主动学习网理念：激发兴趣，挖掘潜力，培优教育网址：电话：[phone]学习最好的朋友是谦虚地向别人学习好的方面！09年秋季五年级第14讲-数论之同余与余数问题教师版Page7of12第14讲数论之同余与余数问题【和差积的余数同余余数的和差积】【1】【解析】（9+7+2）×(9-7)×(7-2)=18×2×5=180，180除以11余4.【2】【解】33、66、99除以3，余数是0，所以只须看表达式124578124578除以3余几．注意：如果a除以3余1a,b除以3余1b.，那a×b除以3所得的余数就是内1a×1b除以3所得的余数因为4、7除以3余1，所以44、77，除以3，余数也是1.因为5、8除以3余2，所以55、88除以3，余数与52,82除以3的余数相同而42=16除以3余1，所以52=42×2除以3余2,82=42×42除以3余l（=1×1）于是124578124578除以3，所得余数与l＋4＋l＋2＋1＋1除以3，所得余数相同，即余数是1.【3】【解】有已知，乙，丙，丁三人取走的七盒中，糖的块数是丁所取糖块数的5倍.八盒糖的总块数是9＋17＋24＋28＋30＋31＋33＋44=216216除以5的余数为1，所以甲取走的一盒除以5余1.因此甲取走的一盒中有31块奶糖.【4】【解法1】甲余11人，乙余36－11=25人.甲团人数与乙团人数的积除以36，余数与11×25除以36的余数相同，即余23.所以最后一卷拍了23张，还可拍36－23=13张.【解法2】因为除去最后一辆车，其它个车里两团代表人数都是36的倍数，所以剩下胶片是最后一辆车里两团代表拍完照留下的.25×11÷36=7……23还可拍36－23=13(张).【5】【分析】任何数乘方的尾数都是4个数一周期．7是7、9、3、1循环，因为2010÷4＝502…2，所以20102017尾数是9.8是8、4、2、6循环，因为98÷4余2，所以9810765868尾数是4.1、被除数÷除数=商………余数，被除数=除数×商+余数2、和差积的余数同余余数的和差积。3、同余：a÷x余r,b÷x余r，则(a-b)是x的倍数，这种技巧常用于求除数的题目。4、求被除数三大类问题:余同(最小公倍数的倍数加余数)，差同（最小公倍数的倍数减差），都不同（剩余定理）。5、整除与余数：除以3或9的余数看数字之和，7、11、13是三位一格，奇位和减偶位和（减不够加7、11、13的若干倍），11也可以一位一格，奇位和减偶位和（减不够加11的若干倍）6、个位数字：自然数的m次方的个位数字都可以看成4次方1个周期。7、有规律的余数问题，常利用“和差积的余数同余余数的和差积”，结合周期简化题目。主动学习网理念：激发兴趣，挖掘潜力，培优教育网址：电话：[phone]学习最好的朋友是谦虚地向别人学习好的方面！09年秋季五年级第14讲-数论之同余与余数问题教师版Page8of129是9、1、9、9循环，因为2009÷4余1，所以20092009尾的数是9.9+9×4=45，个位为5.【6】【分析】求结果除以l0的余数即求从l到2005这2005个数的个位数字是10个一循环的，而对于一个数的幂方的个位数，我们知道它总是4个一循环的，因此把每个加数的个位数按20个一组，则不同组中对应的数字应该是一样的．首先计算123420123420L的个位数字为M.2005个加数中有100组多5个数，100组的个位数是M×100的个位数即O,另外5个数为2001200220012002、2003200420032004、、20052005、，它们和的个位数字是1＋4＋7＋6＋5＝23的个位数3.【7】【分析】同余的性质的应用．【解】∵143≡3(mod7)∴89143≡893(mod7)∵63≡1(mod7)∴898961455143333≡5(mod7).【评析】这类题都是通过找几次方除以7得余数1作为突破，大大简化题目的难度。【巩固】【解析】2011÷8余3，20092011与20093除以8的余数相同，3×