■トーシェント関数と非トーション(その86)

[Q]7^7^7の下2桁を求めよ

[A]整数の下2桁を求めるためにはmod100を計算すればよい。

φ(100)=40  (その85)

(a,m)=1とするときa^φ(m)=1 (modm)  (フェルマー・オイラーの定理)

より,a=7, m=100とすると

x=7^7 (mod40)ならば7^7^7=7^x (mod100)

===================================

7^2=9 (mod40)

7^4=1 (mod40)

7^7=7^4・7^2・7=63=23 (mod40)

7^7^7=7^23 (mod100)

===================================

7^1=7 (mod100)

7^2=49 (mod100)

7^4=1 (mod100)

7^8=1 (mod100)

7^16=1 (mod100)

7^23=7^16・7^4・7^2・7=43 (mod100)

[A]7^7^7の下2桁は43である

===================================