2015年天津公务员考试行测备考：剩余定理的通用解法

“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”

这首诗是说，当一个数除以3余a，除以5余b，除以7余c时，可以这么求出这个数：

，如果求出来的这个数大于105，则减去105，直到小于105为止，就是所求的这个数的最小值了。

这就是现代数论中著名的剩余定理问题。它的基本形式包含在《孙子算经》“物不知数”题的解法之中。到了今天，剩余定理问题已经出现在公务员录用考试当中，如2011年安徽省考就考察了一道相关题目。不过《孙子算经》没有明确地表述这个一般的定理，而且典故所得仅适用于3，5，7三个数，这里我们把它扩展为任何数 。

某数除以A余M，除以B余N，除以C余P，(ABC组为除数，MNP组为余数，XYZ组为凑数所得。)则寻找这样的X、Y、Z ，使得

的X倍除以A余1 (这样对应的

除以A余M)

的Y倍除以B余1 (这样对应的

除以B余N)

的Z倍除以C余1 (对应对应的

除以C余P)

=符合条件的数。然后该数减去A、B、C的最小公倍数直至得到的差小于最小公倍数，那么这个差就是符合条件的最小数。

下面给出一些例题, 考生朋友们可以做一做对这个公式的应用加以熟练：

例1、一个数被3除余1，被4除余2，被5除余4，这个数最小是几?

【解析】题中3、4、5三个数两两互质。 则〔4，5〕=20;〔3，5〕=15;〔3，4〕=12;〔3，4，5〕=60。 为了使20被3除余1，用20×2=40; 使15被4除余1，用15×3=45; 使12被5除余1，用12×3=36。 然后，40×1+45×2+36×4=274， 因为274>60，所以，274-60×4=34，就是所求的数。

例2、一个数被3除余2，被7除余4，被8除余5，这个数最小是几?在1000内符合这样条件的数有几个?

【解析】题中3、7、8三个数两两互质。 则〔7，8〕=56;〔3，8〕=24;〔3，7〕=21;〔3，7，8〕=168。 为了使56被3除余1，用56×2=112; 使24被7除余1，用24×5=120。

使21被8除余1，用21×5=105; 然后，112×2+120×4+105×5=1229， 因为1229>168，所以，1229—168×7=53，就是所求的最小数。 再用(1000-53)/168得5，所以在1000内符合条件的数有6个。

例3、三位数的自然数P满足：除以3余2，除以7余3，除以11余4，则符合条件的自然数P有( )个。

A.5 B.4 C.6 D.7

【解析】题中3、7、11三个数两两互质。则(7，11)=77;(3，11)=33;(3，7)=21。

为了使77被3除余1，用

;使33被7除余1，用

;使21被11除余1，用

;然后，

，因为1445>231，所以，

，就是所求的最小数。再用

得4，由于P要是三位数，故共有4个，选择B。

总结：涉及到这种一般剩余定理的问题可能都会比较繁杂，所以在备考过程中多多练习此类题型，从而达到熟能生巧的境界。

2015年天津公务员考试行测备考：剩余定理的通用解法