关于书学38 mod化简的过程，求高人指点

amyli76

38. 问2^20-n能否被3整除。 （1）n=0  （2）n=1  (3)n=4  最后一个好像是4，不太确定，前两个0和1肯定没记错

2^20-n mod 3
=4^10-n mod 3
=(1+3)^10-n mod 3
=1^10-n mod 3
=1-n mod 3
把n的数字带进去算就好了，第二个和第三个条件可以

对于后三步的化简原理不是特别明白，求高人指点。

LJWISC1OL

同问！！

amyli76

牛牛们现身啊，明天就考了

sdcar2010

2^20-n mod 3
=4^10-n mod 3
=(1+3)^10-n mod 3  ------ becasue 4 = 1 + 3
=1^10-n mod 3 ------- a) (1+3)^10-n = =1^10-n + 3^10-n ; b) [3^10-n mod 3] = 0
=1-n mod 3 --------- 1^10-n =1 (any power of 1 is still 1!)

xjytracy

个人觉得，
2^20-n mod 3
=4^10-n mod 3
=(1+3)^10-n mod 3
=1^10-n mod 3
=1-n mod 3
把n的数字带进去算就好了，第二个和第三个条件可以
因为3^10肯定能被3整除，所以看1^10-N能否被3整除就可以了
很明显，1^10=1，所以题目就化简到了1-n能否被3整除
代入原题给的条件，n=0不可以，n=1的时候，0/3=3 暂时不确定这是不是整除
继续看n=4的时候-3/3=-1可以，n=1和n=4正好差3，也就代表n=1的时候也成立
所以答案是n=1或者n=4

amyli76

大侠们，我不明白的是这一步：(1+3)^10-n = =1^10-n + 3^10-n，能否解释一下这一个环节
学文科的，请谅解哈！

xjytracy

这个就是拆分啊，你要是不会这个的话也可以这么做
2^1=2/3余2, 2^2=4/3余1, 2^3=8/3余2 ,2^4=16/3余1。....
以此类推,余数分别是2,1,2,1。....那么2^20就余1，因为20/2=10
然后就跟前面说的一样了,看1-n能否被3整除

fmsunny

(1+3)^10-n = =1^10-n + 3^10-n????     好像不能这么拆分吧。。。。

lovejane2008

【解法是用了以下的方法，这是我之前下载的一个NN的方法，复制过来分享】


引入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

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

sdcar2010

Typo ?

就是：(M＋N) mod q=(（M mod q）+（N mod q）) mod q

Oh, I got it.  You want to cover the cases where the sum might be larger than q.