余数类题型解题方法

很多同学对余数题都不知如何下手，其实前辈们已经为我们总结了很多方法，为方便大家，我在这里给大家汇总2种最常用，同时也比较便捷的解题思路，希望能帮大家顺利通过考试。注：版权归原作者所有，俺只是负责宣传，：）

如果看不懂推理过程，也不必计较，直接记住方法就可以了。同时希望大家顺手up下，以便帮助后面的同学。
第一种、设通项式求解。

通项S，形式设为S=Am+B，一个乘法因式加一个常量

系数A必为两小通项因式系数的最小公倍数

常量B应该是两个小通项相等时的最小数，也就是最小值的S


例题：4－JJ78(三月84).ds某数除7余3，除4余2，求值。

解：设通项S=Am+B。由题目可知，必同时满足S= 7a+3=4b+2

A同时可被7和4整除，为28（若是S＝6a+3=4b+2，则A＝12）

B为7a+3=4b+2的最小值，为10（a=1.b=2时，S有最小值10）

所以S＝28m＋10

满足这两个条件得出的通项公式，必定同时满足两个小通项。如果不能理解的话，就记住这个方法吧，此类的求通项的问题就能全部，一招搞定啦

原链接

http://forum.chasedream.com/GMAT_Math/thread-51193-1-1.html



第二种：X^n除以a余？类问题
解法见下图

特别说明：一种“个位循环”的解法是错误的，用该法做题很危险。原因见15楼。
在此，贴出特例：
4^50除以3的余数。
解：4^n的个位是以4、6两个数交替的周期为2的循环，根据个位循环法：4^50个位数为6，显然6能被3整除，所以余数“似乎”该为0.被3整除了？！但是4^50=2^100，根本没有3这个因子，不可能被3整除！
事实上：
4^50=(3+1)^50=>1^50除3的余数？=>余1

[b][size=4]好像我的例子举得有点问题。 [/b][/size] 这让很多G友都误解为一定要化为+1……
如果q^n都能化为k*p+1的形式，那大家直接猜余数为1好了……
我的想法是：化成“比该除数小的数”就行了
（注意，是小于除数的数注意该数的次幂！34L以及和想法相同的的同学）
原帖链接

我在自己的讨论稿文档里，求余的时候，都会用到 mod 这个运算符。
mod：模。意思就是求余数。
比如说：5 mod 3=2， 100 mod 11=1
读作：五模三余二，一百模十一余一

这是标准的公式化写法，大家可能不太熟悉，但是知道意思了，其实也很简单。引入Mod，主要是可以用数学公式来写，而且可以把求余数的问题化简成为普通的四则运算的问题，也比较容易表达。
在讲如何求余之前，先来普及一下余数的一些性质。

首先就是余数的加减法：比如说100除以7余2，36除以7余1。那么100+36除以7余几呢？或者100-36除以7余几呢？很显然，只要用100除以7的余数2与36除以7的余数1进行加减就可以得到答案。通过这个例子可以很明显的看出来，余数之间是可以加减的。
总结写成书面的公式的话，就是：(M＋N) mod q=(（M mod q）+（N mod q）) mod q

然后我们再看余数的乘法：我们继续来看上面这个例子，如果要求100*36除以7的余数是多少，该怎么求呢？
我们不妨来这样做：
100=98+2=7*14+2，36=35+1=7*5+1；
这时100*36=（7*14+2）（7*5+1）=7*14*7*5 + 2*7*5 + 7*14*1 + 2*1
很明显，100*36除以7的余数就等于2*1=2
于是我们可以得出这样的一个结论：求M*N除以q的余数，就等于M除以q的余数 乘以 N除以q的余数。

类似的，如果是求N^m 除以q的余数呢？只要我们将N^m=N*N*N*...*N，也就是说分别地用每个N除以q的余数相乘，一共m个，得出的结果再对q求余数，即可求出结果。

举例来说：求11^4除以9的余数。化成公式即是：11^4  mod 9=?
11^4 mod 9 = (9+2)^4 mod 9 = 2^4 mod 9 =16 mod 9 = 7

于是我们可以总结出这样的公式：
M*N mod q=（M mod q）*（N mod q） mod q
（ M^n mod q = （M mod q）^n mod q ）

那么，我们知道了这些性质之后对解题又有什么帮助呢？

As we all know，如果一个数乘以1，还是等于原数；而1的任意次方，还是等于1。
所以在解答这一类的问题的时候，只要我们尽量把计算中的余数凑成与1相关的乘式，结果显然会好算很多的。（或者-1，2之类的比较容易进行计算的数字都可以，因题而异。）

举例说明：求3^11除以8的余数。题目即是：3^11 mod 8=?
  3^11  mod 8
=3^10 * 3^1       （mod 8）
=(3^2)^5*(3^1)    （mod 8）
=9^5  *  3        （mod 8）
=(8+1)^5 * 3      （mod 8）
=1^5 *3           （mod 8）
=3
发现没有，甚至没有去计算什么尾数的规律，答案就算出来了，而且只用了加减乘除。

那么再来看一道题目：求 （2^100）*（3^200） 除以7的余数
先化成计算公式：

(2^100)*(3^200)                          mod 7
=[2^(3*33 + 1)] * [3^(3*66 + 2)]          mod 7
=[(2^3)^33 * 2] * [(3^3)^66 * 3^2]        mod 7
=(8^33 * 2) * (27^66 * 9)                 mod 7
=[(7+1)^33 * 2] * [(28-1)^66 * 9]         mod 7
=(1^33 * 2)* [(-1)^66 * 9]                mod 7
=2*9                                      mod 7
=4

注意：如果余数有负号，就当做负数一样计算。

我步骤写得很详细，但其实只要是熟练了，基本上只要三四步答案一定就出来了，有没有觉得很简单呢？赶紧找一两题来练练手吧，甚至随便写几个数字来做做试试看，像我上面的例题都是临时编的。

相信只要练习了三四道题目，以后再碰到这样的余数题，就会 会心地一笑：小样 ，秒掉你！