试求7的7次方的7次方..7（很多个7的7次方）的末两位数

Question

试求7的7次方的7次方..7（很多个7的7次方）的末两位数

Answer 1

这个数列相当于a[1] = 7,a[n] = 7^a[n-1] (n > 1).
求a[n]末两位数,即求a[n]除以100的余数.
首先证明对任意n,a[n] ≡ -1 (mod 4).
对n = 1,a[1] = 7 ≡ -1 (mod 4).
而对n > 1,由a[n-1]为奇数,a[n] = 7^a[n-1] ≡ (-1)^a[n-1] = -1 (mod 4).
因此a[n] ≡ -1 (mod 4)对任意正整数n成立,即a[n]-3是4的倍数.
又注意到7^4 = 2401 ≡ 1 (mod 100),于是对任意正整数k,有7^(4k) ≡ 1 (mod 100).
因此对n > 1,a[n] = 7^a[n-1] = 7^(a[n-1]-3)·7³ ≡ 7³ = 343 ≡ 43 (mod 100).
即n > 1时,a[n]的末两位数恒为43.