2014年公务员考试行测备考：浅谈剩余定理

公务员考试网

剩余定理是中国古代求解一次同余式组的方法，是数论中一个重要定理，又称孙子定理。
    公元前后的《孙子算经》中有"物不知数"问题："今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何?"答为"23"。明朝程大位用歌谣给出了该题的解法："三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知"，到了18世纪高斯给出剩余定理这一概念，今天张老师带领大家了解一下剩余定理，从而摆脱各位同学之前只用枚举法的困境。
    剩余问题的解法：
    1.特殊情况
    记住口诀：余同加余、和同加和、差同减差。
    (1)余同加余
    【例题1】有一个数除以4余2，除以5余2，除以6余2，问这个数为多少?
    A.120 B.122C.121 D.123
    方法一：代入排除法
    方法二：由题意可知该除以4、5、6均余2，余数相同，属于余同，因此该数满足通项公式N=60n+2 ，(n=0,1,2,3……)，当n=2时，N=122,选择B项。
    注：n前面的系数60是取4、5、6三个除数的最小公倍数。
    (2)和同(除数和余数的和相同)加和
    【例题2】某个数除以5余3，除以6余2，除以7余1，求在0至500内满足这样的自然数有多少个?
    A.3 B.2 C.4 D.5
    方法：此题我们通过观察会发现除数与余数的和相加均为8，则该自然数应满足N=210n+8(n=0,1,2……)因此在0至500以内满足题干条件的自然数有8,218,428三个数。
    注：n前面的系数210是取5、6、7三个除数的最小公倍数。

gwyfour

    (3)差同(除数与余数之差相同)减差
    【例题3】有一个数除以3余2，除以4余3，除以5余4，问此数为多少?
    A. 119 B. 121 C. 129 D. 131
    方法一：代入排除法(略)。
    方法二：通过观察我们会发现除数与余数的差均为1，因此此数满足N=60n-1(n=1,2,3……),可发现A项满足该通项公式。
    注：n前面的系数60是取3、4、5三个除数的最小公倍数
    2.一般情况
    【例题4】三位数的自然数P满足：除以3余2，除以7余3，除以11余4，则符合条件的自然数P有多少个?
    A.5 B. 4 C. 6 D. 7
    【解析】此题中既不余同，也不和同，也不差同，因此上面的特殊情况都不能用，口诀也无法用，但通过观察我们发现，P满足除以3余2，除以7余3两个条件时，在P的基础上加上 4,即(P+4)这个数一定是能够被3整除以及被7整除的，因此(P+4)=21n，所以P=21n-4……①，得到的这个通项公式再与除以11余4进行找通项公式。该自然数P=21n-4=11a+4,等式左边都是被11除，等式左边的余数为10n-4,等式右边的余数为4，我们知道一个数被11除余 4，也可以认为这个数被11除余15，或被11除余26等。根据同余特性可知，等式左边的余数10n-4应与等式右边的余数4,15,26等数值相等。因 为n要取整数，所以取10n-4=26可以得到n=3代入①式得到P=59，所求的59这个数是满足题干三个条件的最小数，所以，满足题干三个条件的数 P=231n+59(n=1,2,3……)，所以在三位数以内的数有290,521,752,983四个数。选择B项。
    练习：一个自然数P同时满足除以3余1，除以4余3，除以7余4，求满足这样条件的三位数共有多少个?
    A.10 B.11 C.12 D.13