R是所有2^n除以1000的餘數所形成之集合

在mod 100下，計算2^n(亦即只看2^n的末兩項)，算到它循環為止
1, 2, 4, 8, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52, 4
第23個數第3個數相同，開始循環，所以循環節為20項

那麼，在mod 1000下，計算2^n(亦即只看2^n的末三項)，
循環節長度勢必為20的倍數，不過不一定從很前面的數開始循環，
所以挑一個大一點的開始算：
2^4≡16(mod 1000)
2^24≡2^4*2^20≡16*576≡216(mod 1000)
2^44≡2^24*2^20≡216*576≡416(mod 1000)
2^64≡2^44*2^20≡416*576≡616(mod 1000)
2^84≡2^64*2^20≡616*576≡816(mod 1000)
2^104≡2^84*2^20≡816*576≡16(mod 1000)

2^104≡2^4≡16(mod 1000)，故循環節是100項
2^101≡2*(2^20)^5≡2*576^5≡752(mod 1000)___不是2，不行
2^102≡752*2≡504(mod 1000)___不是4，不行
2^103≡504*2≡8(mod 1000)
所以實際上是從2^103開始循環，
S≡1+2+4+8+....+2^102≡2^103-1≡8-1≡7(mod 1000)
S除以1000的餘數為7

2011-04-11 00:51:07 補充：
若用Euler定理，循環節長度常常不是剛好為φ(模數)，而是φ(模數)的正因數，
要確定到底是哪一個正因數所要多用的腦細胞未必比較少，
而且循環節的第一項是誰也是個問題；
像本題，φ(1000)=400，但循環節長度卻不是400，而是100，
而且循環節的第一項不是1，也不是2，而是8(亦即除了1,2,4本身以外，沒有任何2的乘冪末三位是1,2,4的了，因為它們不在循環節內)，
然而本題一定要確定循環節長度，不然就會多算，
所以我寧可用較繁瑣但原理簡單的方法。

這是AIME2011考題
(看答案只限000~999即可推知是AIME, 今年的考題我剛好有看過)
會問這題
代表不是考生
就是有興趣要考
程度應該都不錯

2011-04-13 22:27:50 補充：
由於2^n在n>=3時皆為8的倍數
所以只需考慮mod 125就好
φ(125)=125(1-1/5)=100, 由Euler Thm 知 2^100=1 (mod 125)
以下皆mod 125
2^10=24
2^20=576=76
2^40=5776=26
2^50=26*24=624= -1 =\\= 1
2^100=1
所以每100個數循環, 加前三數1,2,4得共103個餘數
故S=1+2+4+...+2^102=2^103-1=2^3-1=7

請問"怡人"的程度為何?

2011-04-10 23:20:17 補充：
我用Euler定理,只不知提問人懂否?