关于GMAT数学中求余数问题的一个简单方法-增强版

阿盖

what about 3^7 mod 15? i am trying to solve this problem but i couldn't get it ><

bowow

231 m 5=1
37 m 5 =2
(231+37) m 5=3
(231-37) m 5=4  <<<---???

芒鞋竹杖

ding

wmn0506

谢谢，很好用。

719870465

明白了，谢谢，很是有用，小时候我们没有学过数论，这应该是在数论里面都有的公式。

719870465

补充一下，当运算结果大于出数时的办法。摘自百度
　　余数有如下一些重要性质（a，b，c均为自然数）：
　　（1）余数小于除数。
　　（2）被除数=除数×商+余数；
　　除数=（被除数-余数）÷商；
　　商=（被除数-余数）÷除数。
　　（3）如果a，b除以c的余数相同，那么a与b的差能被c整除。例如，17与11除以3的余数都是2，所以17-11能被3整除。
　　（4）a与b的和除以c的余数，等于a，b分别除以c的余数之和（或这个和除以c的余数）。例如，23，16除以5的余数分别是3和1，所以（23+16）除以5的余数等于3+1=4。注意：当余数之和大于除数时，所求余数等于余数之和再除以c的余数。例如，23，19除以5的余数分别是3和4，所以（23+19）除以5的余数等于（3+4）除以5的余数。
　　（5）a与b的乘积除以c的余数，等于a，b分别除以c的余数之积（或这个积除以c的余数）。例如，23，16除以5的余数分别是3和1，所以（23×16）除以5的余数等于3×1=3。注意：当余数之积大于除数时，所求余数等于余数之积再除以c的余数。例如，23，19除以5的余数分别是3和4，所以（23×19）除以5的余数等于（3×4）除以5的余数。
　　性质（4）（5）都可以推广到多个自然数的情形。
　　而当被除数小于除数的情况下，商为零，余数就是被除数！

719870465

39.  2^90+3^90 dividable by 5, remainder?
2^90 + 3^90 (mod 5)
= 4^45 + (-2)^90 (mod 5)
=(-1)^45 + 4^45 (mod 5)
=2 * (-1)^45 (mod 5)
= -2 (mod 5)
= 3

-- by 会员 yuling526 (2010/2/5 13:27:50)

我认为应该避免负数的情况，太复杂。我的做法是(不写mod5了)
2^90=4^45=4^44*4=(5-1)^44*4明白了么，让出现-1时的指数变成偶数，这个问题就解决了。
所以2^90mod5=4
同理，3^90mod5=4
所以余数是8，因为8大于5，8mod5=3
大功告成

719870465

我认为可以用两数相减的形式，只要指数是偶数就行。避免错误（当然负数的算法没有错，只是我认为我们不好掌握）所以如果指数是奇数，举个例子4^45mod=4*4^44mod5。4^44=(5-1)^44=1^44=1,1*4=4。

dlcjay

第一个个公式是不是最后多了个mod q

librafp

感谢LZ!