（30^31+31^30）÷13,余数是多少,怎么算的?（30^31+31^30）÷13,我知道余数是3,但不知道怎么算的,请把解释说明白一点,

Question

（30^31+31^30）÷13,余数是多少,怎么算的?
（30^31+31^30）÷13,我知道余数是3,但不知道怎么算的,请把解释说明白一点,

Answer 1

3
30^31+31^30≡4^31+5^30≡2^62+25^15≡(2^6)^10*2^2+(-1)^15≡(-1)^10*4-1≡4-1≡3(mod13)
我们尝试做一下解释：
在带余数除法中,若a=bq+r,其中a,b,q,r分别是被除数,除数,商及余数.
那么a^2除以b的余数等于r^2除以b的余数,因为a^2和r^2相差b的整倍,不知道小学生能否理解?进而对任意正整数n,a^n和r^n除以b的余数相同.
如果这个能懂,那么30^31和4^31除以13的余数相同,因为30除以13余4.
同理31^30和5^30除以13余数相同.4^6=4096除以13余1,4096^5和1^5除以13余数同为1,从而4^31=4096^5*4除以13余4.5^4=625除以13余1,5^30=625^7*25除以13的余数等于1*25除以13的余数结果为12,
因此最终30^31+31^30除以13余数结果为：4+12=16除以13的余数3.