ChaseDream
搜索
返回列表 发新帖
楼主: edmundshi
打印 上一主题 下一主题

余数题通解助您彻底解决一类题目

[精华]   [复制链接]
221#
发表于 2010-10-17 22:39:26 | 只看该作者
谢谢!~
222#
发表于 2010-10-17 23:20:28 | 只看该作者
我来给个定理吧



费马小定理是数论中的一个定理:假如a是一个整数,p是一个素数,那么


如果a不是p的倍数,这个定理也可以写成
223#
发表于 2010-10-17 23:22:44 | 只看该作者
目前为止做的数学题还不到100道。 但是高中数学竞赛的时候用这个定理用的太多了。看到过一道余数题目,直接用费马小定理暴力解决。30秒足够了。
224#
发表于 2010-10-18 00:07:53 | 只看该作者

用这个定理,除数当然最好是质数,如果不是质数,可以写成不同质数相乘的数也可以。
楼主顶楼的题目:

题一,7的50次方除以15

就是7的2次方 除 3 的时候余数是1 ; 7的4次方 去除 5 的时候余数是1

所以 7 的 4次方 除 15 的时候余数是也是1 ; 7的50次方除以15的余数和 7 的二次方(=49) 除以15的余数相同。

显然是4

题二,3的50次方除以8 (不适用费马小定理)
这个不需要费马小定理了,3的2次方除以8余1, 所以3的任何偶数次方除以8都余1。

题三, 13的50次方除以8 (不适用费马小定理)
我想了一下,这个应该用欧拉定理,是费马小定理的扩展定理,更强大。8的欧拉函数是4, 按照欧拉定理说,任何和8互质的数字的4次方除以8都余1。 13的50次方,直接化成13的2次方, 169, 除以8 余1。
225#
发表于 2010-10-18 00:34:03 | 只看该作者
en ; hao
226#
发表于 2010-10-18 10:42:22 | 只看该作者
楼主的方法可以减小底数,  费马小定理(或者欧拉定理)可以直接消幂数,更快!

前提只有一个,底数要和除数互质。  ...不互质?——那么题目就很难看了。


欧拉函数就是——比自己小,而且和自己互质的正整数的个数。 质数n的欧拉函数就是 n-1。

如果是若干个不同质数乘积的数,比如15, 可以分解成 3和5, 对应的n-1是2和4, 他们俩的最小公倍数是4,
除15求余就可以用4倍来消除幂数。50次方直接降为2次方。底数只要不是3的倍数且不是5的倍数就可以了。

记住4的欧拉函数是2; 8 的欧拉函数是4; 9 的欧拉函数是6

稍加练习,这类题目都可以秒杀了。
227#
发表于 2010-10-18 10:50:12 | 只看该作者
比如  10006 的 10003次方, 除 17 ,余数是多少 ?

消幂: 10003 除以16, 余数是3
消底: 10006 除以17, 余数是10

就化解成 10的3次方, 也就是 1000 除以 17 , 余数是 14

再大也不怕了!
228#
发表于 2010-10-18 10:52:32 | 只看该作者
楼主算法的最大问题是要凑 np+1, 有时候会比较累。不过GMAT不会太挑战数学本身的, 向我楼上这种题目是不可能出现的。
229#
发表于 2010-10-18 10:55:20 | 只看该作者
由于欧拉定理的存在,所以这类题目结果是1的可能性相对较大,因为幂数一不小心就是除数欧拉函数的倍数了。
230#
发表于 2010-10-18 18:38:11 | 只看该作者
记下了,很好用,明天上考场。。感谢楼主!
您需要登录后才可以回帖 登录 | 立即注册

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

手机版|ChaseDream|GMT+8, 2025-1-8 23:06
京公网安备11010202008513号 京ICP证101109号 京ICP备12012021号

ChaseDream 论坛

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

返回顶部