求 2^1000000 除以 77 的余数

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，
欢迎大家一起来想想如何解答：
2^(100000)次方除以77的餘數為何?
(a)17 (b)23 (c)36 (d) 42

根據
2^(100000)=1 (mod11)    2^(100000)=2 (mod7)
可知 (b) 最有可能  , 這是為什麼?
另外，詳細的方法如何處理?

fungarwai

http://baike.baidu.com/view/157384.htm
x=1(mod11)
x=2(mod7)
M1=7,M2=11
7M1';=1(mod11),M1';=8
11M2';=1(mod7),M2';=2
M1';M1b1+M2';M2b2=56+44=100=23

moranhuishou

2^10(mod 77)=23
23^10(mod 77)=23
...

luyuanhong