试求不大于100,且使11|（3^n+7^n+4）成立的自然数n的和.

Question

试求不大于100,且使11|（3^n+7^n+4）成立的自然数n的和.

Answer 1

3 ≡ 3 (mod 11)
3^2 ≡ 9 (mod 11)
3^3 ≡ 5 (mod 11)
3^4 ≡ 4 (mod 11)
3^5 ≡ 1 (mod 11)
所以,3^n (mod 11) 是以5个数为循环的序列：3、9、5、4、1
同理可得：7^n (mod 11) 是以10个数为循环的序列：7、5、2、3、10、4、6、9、8、1
所以,3^n + 7^n (mod 11) 是以10个数为循环的序列：10、3、7、7、0、7、4、3、1、2
所以,只有当 n ≡ 3、4、6 (mod 10) 时,3^n + 7^n + 4 才能被11整除.
n不大于100时,求和：
sum_{k从0到9} [(10k+3) + (10k+4) + (10k+6)]
= sum_{k从0到9} (30k+13)
= 30*45 + 13*10
= 1480