由 司馬特 於 星期六 一月 21, 2012 1:15 am
借用 哈哈樂天 的計算成果
3^9=19683
3^10=59049
3^20=1000b+401
3^40=1000c+801
3^80=1000d+601
到這裡就可以看出來 3^100 mod 1000 = 401*601= (400+1)(600+1) = 240000+10000+1
也就是說 3^100 mod 1000 = 1
則
3^2009 mod 1000 = (3^100)^20 X 3^9 =19683
故
3^2009 mod 1000 = 1