ChaseDream
搜索
返回列表 发新帖
查看: 32414|回复: 56

余数题通解V2.0

[精华]   [复制链接]
发表于 2010-10-18 11:34:56 | 显示全部楼层 |阅读模式




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)

 楼主| 发表于 2010-10-18 11:51:27 | 显示全部楼层
关于欧拉函数的使用

GMAT可能考到的情况中, 除数肯定是小于20的。但是欧拉函数是靠数数数出来的(数数,数),数数是考场上最容易出错的计算步骤!比如8的欧拉函数, 就是比8小而且和8互质的数字(1,3,5,7),一共4个,就是4。但是数的时候很容易把1给漏了!

那就先分析一下吧:

除数1-4 不可能考, 选项都不够放呀

5 6 7 10 11 13 14 15 17 19 这些数字, 要么是质数,要么是两个质数的乘积, 所以都不需要求欧拉函数。

剩下来 8 9 12 16 18 20  (这些数是4的倍数或者9的倍数), 对应的欧拉函:

8 —— 4
9 —— 6
12 —— 4
16 —— 8
20 —— 8

记住了就可以了,特别是前3个。 或者当场数 —— 但是记住,数出来肯定是 4 、6 或者8。
发表于 2010-10-18 12:03:54 | 显示全部楼层
太牛了,这是数论了吧?
 楼主| 发表于 2010-10-18 17:51:37 | 显示全部楼层
15的欧拉函数是8, 但是3-1=2 , 5-1=4 , 2和4的最小公倍数是4, 所以这里把15的欧拉函数当成4也没有问题。而且这样算比数欧拉函数更快,更准。
 楼主| 发表于 2010-10-18 18:08:52 | 显示全部楼层
我再出个简明操作手册


A 的 B 次方, 除以 C ,余数是多少?

附加条件 : A ,C 互质

解法:  

第一步: 如果 A 比 C 大, 那么直接用A 除以 C 求出余数 A' , 把A 替换掉。

第二部: 求C的欧拉函数, 如果C是质数,欧拉函数就是 C-1; 如果C是几个不同的质数相乘,那么就取这些质数各自减一之后的那组数的最小公倍数;如果是 8 9 12 16 18 20, 那么对应是 4 6 4 8 6 8。  求出了的欧拉函数值为 o 。 不需要记住欧拉函数,可以做题的时候数出来。

第三部: 如果B比o大, 那么B直接除以o求出余数B' , 把B替换掉。

第四部:直接算吧,数字已经很小了。



举个例子 : 10006 的 10003次方, 除 17 的余数
第一步: 10006 除以 17 余 10  , 用10 替换  10006
第二部: 17的欧拉数是16
第三部: 10003 除以16 余3, 用3替代 10003
第四部: 求出 10 的3次方, 除以 17 , 余数是14





 楼主| 发表于 2010-10-18 18:28:50 | 显示全部楼层
欧拉函数的定义: 正整数N的欧拉函数,就是比N小,而且和N互质的正整数的个数。
举个例子 10, 和  1,3,7,9 互质, 10的欧拉函数就是4。


(数的时候不要忘了把1数进去!)


20以内的欧拉函数(或替代欧拉函数)表:

5  —— 4  —— 质数,后面质数都不标了
6  —— 2  —— 6=2x3, 1和2的公倍数,实际上也是6的欧拉数
7 —— 6  
8 —— 4  —— 欧拉函数
9 —— 6 ——  欧拉函数
10 —— 4 —— 10=2x5, 1和4的公倍数, 实际上也是10的欧拉数
11 —— 10
12 —— 4 —— 欧拉函数
13 —— 11
14 —— 6 —— 14=2x7, 1和6的公倍数, 实际上也是14的欧拉数
15 —— 4 —— 15=3x5 , 2和4的公倍数, 可替代欧拉数, 而15真正欧拉数是8
16 —— 8 —— 欧拉函数
17 —— 16
18 —— 6 ——  欧拉函数
19 —— 18
20 —— 8 ——  欧拉函数

不用记住,有个印象就可以,做题的时候数就可以。 20以内,非质数的欧拉函数全都是 4、6、8 ,除了6的欧拉数是2以外。
发表于 2010-10-18 18:38:42 | 显示全部楼层
xie xie louzhu 勤苦了
发表于 2010-10-18 22:39:03 | 显示全部楼层
牛帖留名!
发表于 2010-10-19 00:52:46 | 显示全部楼层
这个方法希望有多点案例
发表于 2010-10-20 04:55:03 | 显示全部楼层
如果超出欧拉定理的适用范围, a 和n 不互质, 该怎么办呢?
您需要登录后才可以回帖 登录 | 立即注册

Mark一下! 看一下! 顶楼主! 感谢分享! 快速回复:

手机版|ChaseDream|GMT+8, 2024-3-29 10:05
京公网安备11010202008513号 京ICP证101109号 京ICP备12012021号

ChaseDream 论坛

© 2003-2023 ChaseDream.com. All Rights Reserved.

返回顶部