余数题通解V2.0

zhlee

edmundshi 给出了一个方法：  （http://forum.chasedream.com/GMAT_Math/thread-403174-1-1.html）


对于 a^n 除以 p 的余数 可以化为


(bp + k)^n 除以 p


从而 变成解  k^n 除以 p


通过对 b 和 n 调整， 把 k 逐渐转换为1  


具体解法看 http://forum.chasedream.com/GMAT_Math/thread-403174-1-1.html


我稍微补充一个定理。


　　欧拉定理（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互素，(a,n) = 1，则
　　a^φ(n) ≡ 1 (mod n)


如果 n 是质数 那么 φ(n)=n-1 ，这个定理就变成了费马小定理。


余数是1， 意味着可以 φ(n)的倍数可以直接消除！
定理不用记忆， 我们直接做题目：


题一，7^50 除以15 的余数


15分解为 3 和 5 两个质数 3-1=2 、 5-1=4


按照费马小定理，7平方 除 3 的时候余数是1 ； 7的4次方 去除 5 的余数是1

所以7 的 4次方 除 15 的时候余数是也是1


7^50 ≡ ((7^4)^12)*7^2  ≡ 7^2 = 49 ≡  4  (mod 15)



题二，3^50 除以 8 的余数
φ(8)=4
3^50 ≡ 3^2 ≡ 1 (mod 8)

题三， 13^50除以8  的余数
φ(8)=4
13^50 ≡ 13^2 ≡ 1 (mod 8)


题目四： 10006 的 10003次方， 除 17 的余数
10006 ≡ 10 (mod 17)
10003 ≡ 3 (mod 16)
10006 ^ 10003 ≡  10^3 = 1000 ≡ 14 (mod 17)

0320zjx

顶楼主！               

XXINYI-

真的绝世好贴！

auttoautto

欧拉函数的定义： 正整数N的欧拉函数，就是比N小，而且和N互质的正整数的个数。
关于欧拉函数， 补充一下算法， 千万不要去数数，很容易数错！！！
1. n为质数， φ(n) =n-1; 例如 φ(7)=6 ；φ(3)=2；
2. n 为某个数的次幂 n= a^m , φ(n) =a^m - a^(m-1) ； 例如 8=2^3 ==> φ(8)=2^3-2^2=4 ； φ(4) =2
3. n 为合数， 因式分解把n 化为质数的乘积， 然后相乘 φ(n*m)=φ(n)*φ(m); 例如 φ(12)=φ(3)*φ(4) =2*2=4
在考场上，不管多大的数，都可以算出具体的欧拉函数！

auttoautto

欧拉函数的定义： 正整数N的欧拉函数，就是比N小，而且和N互质的正整数的个数。
关于欧拉函数， 补充一下算法， 千万不要去数数，很容易数错！！！
1. n为质数， φ(n) =n-1; 例如 φ(7)=6 ；φ(3)=2；
2. n 为某个数的次幂 n= a^m , φ(n) =a^m - a^(m-1) ； 例如 8=2^3 ==> φ(8)=2^3-2^2=4 ； φ(4) =2
3. n 为合数， 因式分解把n 化为质数的乘积， 然后相乘 φ(n*m)=φ(n)*φ(m); 例如 φ(12)=φ(3)*φ(4) =2*2=4
在考场上，不管多大的数，都可以算出具体的欧拉函数！

VVVVagrant

顶楼主！               

Ariafox

顶?

迷迷靡靡谜谜

感谢分享！               

lena410

zhlee 发表于 2010-10-18 18:28
欧拉函数的定义： 正整数N的欧拉函数，就是比N小，而且和N互质的正整数的个数。举个例子 10， 和  1,3 ...

13的欧拉应该是12吧

核桃英雄

Mark一下！