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

yandong1208

谢谢！~

zhlee

我来给个定理吧



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


如果a不是p的倍数，这个定理也可以写成

zhlee

目前为止做的数学题还不到100道。 但是高中数学竞赛的时候用这个定理用的太多了。看到过一道余数题目，直接用费马小定理暴力解决。30秒足够了。

zhlee

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

题一，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。

tinnashen

en ; hao

zhlee

楼主的方法可以减小底数，  费马小定理（或者欧拉定理）可以直接消幂数，更快！

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


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

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

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

稍加练习，这类题目都可以秒杀了。

zhlee

比如  10006 的 10003次方， 除 17 ，余数是多少 ？

消幂： 10003 除以16， 余数是3
消底： 10006 除以17， 余数是10

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

再大也不怕了！

zhlee

楼主算法的最大问题是要凑 np+1， 有时候会比较累。不过GMAT不会太挑战数学本身的， 向我楼上这种题目是不可能出现的。

zhlee

由于欧拉定理的存在，所以这类题目结果是1的可能性相对较大，因为幂数一不小心就是除数欧拉函数的倍数了。

timzf

记下了，很好用，明天上考场。。感谢楼主！