余数问题

数论模块数论题的特点就是简洁明了，信息量看起来往往比较少，所以很多同学在见到数论题的时候总会觉得无从入手，因此，做数论题时很重要的一点就是寻找突破口，走对方向。另外，数论模块的另一个特点就是：知识点非常多。但相比组合而言，数论至少显得更“有法可依”，考场上一定要敢去思考数论题，“战略上藐视，战术上重视”，战略上要相信，考题所用的知识点绝对不会超出小学知识范畴，而考前我们能做的，就是好好研究一下战术——如何应对每一类题目。我就不详细讲每一个知识点（确实非常之多，关键在于平常积累），在这里，我就解数论题的三个突破口来谈谈考场上如何找到数论题的解题思路。还是那个我在课堂上讲过很多遍的例子：任意找一个数，我们都可以从三个角度去分析它，例如154：（1）我们可以说它是一百五十四，在这里，1是百位上的数字，它代表1个100，5代表5个10，4代表4个1，这可以说是位值原理的角度；（2）154＝2×7×11，分解质因数；（3）154除以5余4，除以9余1，我们可以研究它除以任意一个数所得的商和余数；以上三种角度分析一个数也映射出数论体系的三大块内容，同时也是我们分析数论问题的三种方式，三个突破口。下面我来详细讲讲每一个角度。一、位值原理和整除。其实所有数字的整除特性都是利用位值原理推导出来的，从这个也反映出了学习数论的一个策略：找到知识点的源头，知道它们是怎么来的，这样就不用背那么多知识点了。言归正传，什么样的题目我们往这个角度去思考呢？有些题目比较明显，就不用多说了，举个最简单的例子：55□39能被11整除，请问□是几？这种题就直接利用整除特性就OK了。考得比较多的，比如这样的题目：“一个三位数A的三个数字所组成的最大三位数与最小三位数的差仍是数A，这个三位数A是多少？”题中提到了X位数或者提到了这个数里面的某几位数字的，可以考虑用位值原理。利用位值原理对题目进行“翻译”——也就是把文字翻译成数学语言（数学式子），再结合其他的知识点去“加工”，一步步地解答它。这就是我常常对学生说的：不要对着题目干想，一定要动笔，尝试“翻译”题目。借用薛威阳老师的理念，就是“把思路放在纸上”。二、分解质因数。这也是约数、倍数、质数、合数、平方数的核心。所以涉及到约倍质合及平方数的问题就可以从分解质因数的角度去研究研究，题目中如果有具体数字，不妨对其进行质因数分解，从它的因子中寻找解题思路。如果题目中没有给定具体数字，而是让你求这个数，那么也可以从题目中给的信息去探索这个数含有的质因子及其个数。这部分内容的知识点最多，同学们务必熟练掌握，否则一切都是空谈。三、余数。常考的余数问题基本可以分成四类：带余除法、余数周期问题、同余问题、“物不知其数”，解题时关键要分清楚它到底是想考你什么，这样才能拿出正确的破解方法。下面我简单谈谈这四类问题：1、带余除法。最关键就是理清被除数、除数、商、余数的关系，特别需要注意的是，余数肯定小于除数。出题者常常会在这里设置陷阱。2、余数周期。这其中又分为递推数列（给一串数，要求第X个数除以某个数的余数）和次幂（求一个数的X次方除以某个数的余数）相关的余数问题，处理这两类问题一个最直接的做法就是找规律，因为它们除以某数的余数都是有周期的。3、同余问题。很多人分不清同余问题和“物不知其数”问题的区别。举个例子：“一个自然数除429、791、500所得的余数分别是a＋5、2a、a，求这个自然数和a的值。”这是同余问题，已知被除数和余数，求除数。这种问题就是想办法把余数都化为相同的数，然后两两做差求最大公约数。4、“物不知其数”。与同余问题对应的，举个例子：“一个数除以3余2，除以5余3，除以7余2，求这个数。”已知除数和余数，求被除数。接这种问题又两个万能方法：逐级满足和中国剩余定理。但是考试往往不考这两个方法，这两个方法往往也比较繁琐。考试题里不妨去研究研究题中给的除数和对应的余数的关系（和或差），若他们的和或差相同，那么就有简单的解题方法（即所谓“加同补”、“减同余”），实在没有，再考虑逐级满足和中国剩余定理。最后我把小学数论里需要掌握的知识点列个简单的大纲，务必拿出来复习一下，如果这些基础都没有，那上面的这些都是空谈，甚至都看不懂。1、奇偶性质；2、特殊数（2、5、3、9、11、13、……）的整除特定和余数特性；3、质数、合数相关性质，判断一个数是质数或合数的方法，分解质因数；4、约数、倍数、最大公约数、最小公倍数的求法和相关性质，约数个数定理；5、完全平方数的性质；6、带余除法，弃九法，同余问题和“物不知其数”问题的几个处理方法。余数问题---四大绝技（加同补；减同余；中国剩余定理；逐步约束法）“差同减差，和同加和，余同取余，最小公倍加”这是同余问题的口诀。所谓同余问题，就是给出“一个数除以几个不同的数”的余数，反求这个数，称作同余问题。首先要对这几个不同的数的最小公倍数心中有数，下面以4、5、6为例，请记住它们的最小公倍数是60。1、差同减差：用一个数除以几个不同的数，得到的余数，与除数的差相同，此时反求的这个数，可以选除数的最小公倍数，减去这个相同的差数，称为：“差同减差”。例：“一个数除以4余1，除以5余2，除以6余3”，因为4-1=5-2=6-3=3，所以取-3，表示为60n-3。【60后面的“n”请见4、，下同】2、和同加和：用一个数除以几个不同的数，得到的余数，与除数的和相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的和数，称为：“和同加和”。例：“一个数除以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中的60n）都满足条件，称为：“最小公倍加”，也称为：“公倍数作周期”。弃九法从第4讲知道，如果一个数的各个数位上的数字之和能被9整除，那么这个数能被9整除；如果一个数各个数位上的数字之和被9除余数是几，那么这个数被9除的余数也一定是几。利用这个性质可以迅速地判断一个数能否被9整除或者求出被9除的余数是几。例如，3645732这个数，各个数位上的数字之和为3＋6＋4＋5＋7＋3＋2＝30，30被9除余3，所以3645732这个数不能被9整除，且被9除后余数为3。但是，当一个数的数位较多时，这种计算麻烦且易错。有没有更简便的方法呢？因为我们只是判断这个式子被9除的余数，所以凡是若干个数的和是9时，就把这些数划掉，如3＋6＝9，4＋5＝9，7＋2＝9，把这些数划掉后，最多只剩下一个3（如下图），所以这个数除以9的余数是3。这种将和为9或9的倍数的数字划掉，用剩下的数字和求除以9的余数的方法，叫做弃九法。一个数被9除的余数叫做这个数的九余数。利用弃九法可以计算一个数的九余数，还可以检验四则运算的正确性。例1求多位数7645821369815436715除以9的余数。分析与解：利用弃九法，将和为9的数依次划掉。只剩下7，6，1，5四个数，这时口算一下即可。口算知，7，6，5的和是9的倍数，又可划掉，只剩下1。所以这个多位数除以9余1。例2将自然数1，2，3，…依次无间隔地写下去组成一个数1234567891011213…如果一直写到自然数100，那么所得的数除以9的余数是多少？分析与解：因为这个数太大，全部写出来很麻烦，在使用弃九法时不能逐个划掉和为9或9的倍数的数，所以要配合适当的分析。我们已经熟知1＋2＋3＋…＋9＝45，而45是9的倍数，所以每一组1，2，3，…，9都可以划掉。在1～99这九十九个数中，个位数有十组1，2，3，…，9，都可划掉；十位数也有十组1，2，3，…，9，也都划掉。这样在这个大数中，除了0以外，只剩下最后的100中的数字1。所以这个数除以9余1。在上面的解法中，并没有计算出这个数各个数位上的数字和，而是利用弃九法分析求解。本题还有其它简捷的解法。因为一个数与它的各个数位上的数字之和除以9的余数相同，所以题中这个数各个数位上的数字之和，与1＋2＋…＋100除以9的余数相同。利用高斯求和法，知此和是5050。因为5050的数字和为5＋0＋5＋0=10，利用弃九法，弃去一个9余1，故5050除以9余1。因此题中的数除以9余1。例3检验下面的加法算式是否正确：2638457＋3521983＋6745785＝12907225。分析与解：若干个加数的九余数相加，所得和的九余数应当等于这些加数的和的九余数。如果不等，那么这个加法算式肯定不正确。上式中，三个加数的九余数依次为8，4，6，8+4+6的九余数为0；和的九余数为1。因为0≠1，所以这个算式不正确。例4检验下面的减法算式是否正确：7832145-2167953＝5664192。分析与解：被减数的九余数减去减数的九余数（若不够减，可在被减数的九余数上加9，然后再减）应当等于差的九余数。如果不等，那么这个减法计算肯定不正确。上式中被减数的九余数是3，减数的九余数是6，由（9+3）-6＝6知，原题等号左边的九余数是6。等号右边的九余数也是6。因为6＝6，所以这个减法运算可能正确。值得注意的是，这里我们用的是“可能正确”。利用弃九法检验加法、减法、乘法（见例5）运算的结果是否正确时，如果等号两边的九余数不相等，那么这个算式肯定不正确；如果等号两边的九余数相等，那么还不能确定算式是否正确，因为九余数只有0，1，2，…，8九种情况，不同的数可能有相同的九余数。所以用弃九法检验运算的正确性，只是一种粗略的检验。例5检验下面的乘法算式是否正确：46876×9537＝447156412。分析与解：两个因数的九余数相乘，所得的数的九余数应当等于两个因数的乘积的九余数。如果不等，那么这个乘法计算肯定不正确。上式中，被乘数的九余数是4，乘数的九余数是6，4×6＝24，24的九余数是6。乘积的九余数是7。6≠7，所以这个算式不正确。说明：因为除法是乘法的逆运算，被除数=除数×商+余数，所以当余数为零时，利用弃九法验算除法可化为用弃九法去验算乘法。例如，检验383801÷253=1517的正确性，只需检验1517×253=383801的正确性。练习51.求下列各数除以9的余数：（1）7468251；（2）36298745；（3）2657348；（4）6678254193。2.求下列各式除以9的余数：（1）67235＋82564；（2）97256-47823；（3）2783×6451；（4）3477+265×841。3.用弃九法检验下列各题计算的正确性：（1）228×222＝50616；（2）334×336＝112224；（3）23372428÷6236＝3748；（4）12345÷6789＝83810105。4.有一个2000位的数A能被9整除，数A的各个数位上的数字之和是B，数B的各个数位上的数字之和是C，数C的各个数位上的数字之和是D。求D。逐步约束法一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班有多少学生？解法：题目可以看成，除3余2，除5余3，除7余4。没有同余的情况，用的方法是“逐步约束法”，就是从“除7余4的数”中找出符合“除5余3的数”，就是再7上一直加4，直到所得的数除5余3。得出数为18，下面只要在18上一直加7和5得最小公倍数35，直到满足“除3余2”4＋7＝1111＋7＝1818＋35＝53这种方法也可以解“中国剩余定理”解的题目。比“中国剩余定理”更好理解，我觉的速度上会比那个繁琐的公式化的解题更快。中国剩余定理我国古代数学名著《孙子算经》中，记载这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。”用现在的话来说就是：“有一批物品，3个3个地数余2个，5个5个地数余3个，7个7个地数余2个，问这批物