Question

2的100次方除以35的余数是多少？

Answer 1

2^12=4096，除以35余数是1。
2^100=(2^12)^8*2^4
它除以35，余数为1^8*16=16

Answer 2

2^100=32^20=(35–3)^20
=C(20 ，0) 35^20·(–3)^0+C(20，1) 35^19·(–3)+……+C(20，19) 35·(–3)^19+C(20，20) (–3)^20
所以2^100除以35的余数和3^20除以35的余数相同
3^20=9·27^6=9·(35–8)^6
=9[35^6+6·35^5·(–8)+……+6·35·(–8)^5+(–8)^6]
9·8^6=9·64³=9·(35+29)³
=9·(35³+3·35²·29+3·35·29²+29³)
9·29^3=9·(35–6)³
=9(35³–3·35²·6+3·35·6²–6³)
–9·6³=–9×6×36=–54×(35+1)
=(–70+16)(35+1)
=–70·35–70+16·35+16
所以2^100除以35余16