a^20の下2桁を考える
【Step1】2^20の下2桁
x=2^20=4^10=(5-1)^10=∑(-1)^(10-i)C[10,i]5^i
i≧2のとき、5^i≡0 (mod 25)
x≡-C[10,1]5+1≡1 (mod 25)
x≡0 (mod 4)
よって、x≡76 (mod 100)
76^2=5776≡76 (mod 100)より、
76^n≡76 (mod 100)
(2^k)^20=(2^20)^k≡76^k≡76 (mod 100)
【Step2】5^20の下2桁
5^2=25
25^2=625≡25 (mod 100)より、
25^n≡25 (mod 100)
5^20=(5^2)^10≡25^10≡25 (mod 100)
(5^k)^20=(5^20)^k≡25^k≡25 (mod 100)
【Step3】a≡±1 (mod 10)
a^2≡1 (mod 10)→a^2=10t+1とおける
a^20=(a^2)^10=(10t+1)^10=∑C[10,i](10t)^i
i≧2のとき、(10t)^i≡0 (mod 100)
a^2≡C[10,1](10t)+1≡1 (mod 100)
【Step4】a≡±3 (mod 10)
a^2≡9≡-1 (mod 10)→a^2=10s-1とおける
a^20=(a^2)^10=(10s-1)^10
=∑{C[10,i](10s)^i×(-1)^(10-i)}
i≧2のとき、(10s)^i≡0 (mod 100)
a^2≡-C[10,1](10s)+1≡1 (mod 100)
【Step5】まとめ (mod 100)を略す
①2^20≡76→(2^k)^20≡76
②5^20≡25→(5^k)^20≡25
③2,5以外の素数p
p^20≡1→(p^k)^20≡1
【Step6】a^20の下2桁
a=(2^p)×(5^q)×A
Aは2,5以外の素数の積
①p＞0,q＞0のとき、a^20≡0
②p＞0,q=0のとき、a^20≡76
③p=0,q＞0のとき、a^20≡25
④p=q=0のとき、a^20≡1
言い換えれば、
①aの一の位が0→a^20≡0
②aの一の位が0以外の偶数→a^20≡76
③aの一の位が5→a^20≡25
④それ以外→a^20≡1
(2024/8/17)
