Question

数论周期问题，高手进

An=3，An=3^A（n-1）
1.求An的最后一位数字
2.求An的最后两位数字
我们竞赛老师昨天讲了，方法比这个要简单，不过谢谢你了！

Answer 1

以下以==表示同余。
题:A1=3,An=3^A（n-1）,求An mod 100

引理：
a,m互质，a^ φ(m)==1 mod m
推论：a,m互质，r == s mod φ(m),则a^r==a^s mod m
这个结论我按以下方式使用：
a^r==a^[r mod φ(m)] mod m
注：
其中φ(m)是欧拉函数，即<m且与m互质的自然数的个数。
例如，φ(5)＝4，φ(p^r)=p^r*(1-1/p)
另外，φ(m)是可乘函数:若a,b互质，则φ(ab)=φ(a)φ(b)
于是:φ(100)=φ(4)φ(25)=2*20=40

解:
易见
(I) An mod 2==1
(II) An mod 4 ==(-1)^A（n-1）==-1==3
(III)A1 mod 5==3
n>1时,An==3^[A(n-1)mod4]==3^3==2 mod 5
(IV) A1 mod 20 ==3
由(II)(III),建立同余式组,解得
n>1时,An mod 20==7
从而
n>1时,An mod 25==3^[A(n-1)mod20]
于是:A2 mod 25==2
n>2时,An mod 25 ==3＾7mod 25==27*27*3==2*2*3==12

综上述,
A1,A2mod 100==3,27
n>2时,An mod 4 ==3, An mod 25==12
解同余式得:An mod 100 ==87

当然还有其他方法，但就计算而言，我以为以上方法最简。