关于求余的公式有几个疑问啊

雪梦儿

一位NN贴的帖子：M*N mod q=（M mod q）*（N mod q） mod q
（ M^n mod q = （M mod q）^n mod q ）

3^2006 MOD 5 =4
可是如果按照 M^n mod q = （M mod q）^n mod q来算。。。是算不到4的啊？

另外我经常会看到如果比如
原帖：http://forum.chasedream.com/GMAT_Math/thread-432976-1-2.html
3^2006 mod 5，就是(3mod5)^(2006mod 5)可是这样算不到4啊。。。

3 mod 5=3,2006 mod 5=1,那就是3的1次方，不是还是3吗？
另外经常看到（

雪梦儿

发现两天了。。。都米人理我。。。

lhnstefsun

可以算到的：(3^2006) mod 5=(9^1003) mod 5=[ (9 mod 5)^1003] mod 5=(4^1003) mod 5
=[(4^1002)*4]mod 5=[(16^501)*4]mod 5={[(16 mod 5)^501]mod 5 *(4 mod 5)}mod 5
=[(1 mod 5)*(4 mod 5)]mod 5= 4 mod 5=4

lhnstefsun

那么再来看一道题目：求 （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
这是那个版主给的例子，你看看是不是这样算的

雪梦儿

嗯，这个地方我知道，可是我是对于他给出的那个公式有疑问，因为那个公式如果直接套用的话，3^2006 mod 5的计算会更简单，可是算出来的答案是错误的。。。
它写M^N mod Q= (M mod Q)^(N mod Q)
可是你也可以试试。。。算出来不对的。。。