网站导航   4000-006-150  
小站教育
GMAT成绩单完美解读
学生选择在小站备考:30天 525214名,今日申请2797人    备考咨询 >>

做好GMAT数学余数题 擅用欧拉定理秒选难题

2015年02月19日14:16 来源:小站整理
参与(0) 阅读(7822)
摘要:欧拉定理(也称费马-欧拉定理)是一个关于同余的性质。本文介绍用欧拉定理解决GMAT数学考试中的余数题。

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

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

余数是1, 意味着可以 φ(n)的倍数可以直接消除!

做好GMAT数学余数题 擅用欧拉定理秒选难题图1

定理不用记忆, 我们直接做题目:

题一: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)

做好GMAT数学余数题 擅用欧拉定理秒选难题图2

关于欧拉函数的使用

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。

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

欧拉函数的定义: 正整数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以外。

最后,如果超出欧拉定理的适用范围, a 和n 不互质, 该怎么办呢?

约分!约到互质不就可以了!不过别忘了最后要把余数再乘以被约掉的数。

求: 3^7 除以 15 的余数

除数和被除数都除以3, 约分以后 ,先求 3^6 除以 5 的余数,

按照上面的方法,算出来余数是4,

再把余数成以约分的数 3

所以 3^7 除以 15 的余数 是 12。

不过你见过余数题上来先约分的么?这种题目出现的可能性几乎为0。

特别申明:本文内容来源网络,版权归原作者所有,如有侵权请立即与我们联系contactus@zhan.com,我们将及时处理。

GMAT备考资料免费领取

免费领取
看完仍有疑问?想要更详细的答案?
备考问题一键咨询提分方案
获取专业解答

相关文章

【GMAT考点】数学几何代数10大知识重点详细汇总 一眼看穿数学难题所在 教你发现GMAT真题中的隐藏条件 GMAT数学排列组合题怎样保证正确率?重要解题步骤实例讲解 GMAT数学2大题型分析 PS和DS解题思路详细介绍 GMAT数学题中最常见的10种易错细节举例说明 如何才能用好各类学习资源?GMAT数学深度备考心得汇总 警惕GMAT数学满分大敌 几何比较题常见做法分享 【备考心经】GMAT数学考前也要做好热身运动

专题推荐

日排行
周排行
版权申明| 隐私保护| 意见反馈| 联系我们| 关于我们| 网站地图| 最新资讯
© 2011-2024 ZHAN.com All Rights Reserved. 沪ICP备13042692号-23 举报电话:4000-006-150
沪公网安备 31010602002658号
增值电信业务经营许可证:沪B2-20180682