山东公务员考试行测辅导:同余问题中的剩余定理

山东公务员考试行测辅导:同余问题中的剩余定理

　　2013年山东省公务员考试笔试将于4月13日进行，华图教育山东分校(http://sd.huatu.com/)特整理一些山东公务员考试的行测备考指导供考生参考，希望对考生备考行测有所帮助。

　　余数问题中的一个重要问题就是同余问题，在同余问题解决过程中，华图公务员考试研究中心(www.huatu.com)推荐代入法和口诀法两大类。其中口诀法是公倍数做周期，余同取余，和同加和，差同减差的应用，但是有时候会出现余不同，和不同并且差也不同的现象，这就需要我们采用剩余定理进行解决。

　　剩余定理的原理是在“孙子问题”现代数论中的一个一次同余问题，它最早出现在我国公元四世纪的数学著作《孙子算经》中。《孙子算经》卷下“物不知数”题说：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何?显然，这相当于求不定方程组

　　N=3x+2，N=5y+3，N=7x+2

　　的正整数解N，或用现代数论符号表示，等价于解下列的一次同余组：

　　《孙子算经》所给答案是N=23。由于孙子问题数据比较简单，这个答数通过试算也可以得到。但是《孙子算经》并不是这样做的。“物不知数”题的术文指出解题的方法：三三数之，取数七十，与余数二相乘;五五数之，取数二十一，与余数三相乘;七七数之，取数十五，与余数二相乘。将诸乘积相加，然后减去一百零五的倍数。列成算式就是：

　　N=70×3+21×3+15×2-2×105。

　　这里105是模数3、5、7的最小公倍数，容易看出，《孙子算经》给出的是符合条件的最小正整数。对于一般余数的情形，《孙子算经》术文指出，只要把上述算法中的余数2、3、2分别换成新的余数就行了。以R1、R2、R3表示这些余数，那么《孙子算经》相当于给出公式

　　N=70×R1+21×R2+15×R3-P×105(p是整数)。

　　孙子算法的关键，在于70、21和15这三个数的确定。后来流传的《孙子歌》中所说“七十稀”、“廿一枝”和“正半月”，就是暗指这三个关键的数字。《孙子算经》没有说明这三个数的来历。实际上，它们具有如下特性：

　　也就是说，这三个数可以从最小公倍数M=3×5×7=105中各约去模数3、5、7后，再分别乘以整数2、1、1而得到。假令k1=2，K2=1，K3=1，那么整数Ki(i=1，2，3)的选取使所得到的三数70、21、15被相应模数相除的时候余数都是1。由此出发，立即可以推出，在余数是R1、R2、R3的情况下，

　　综合以上三式又可得到