last 3 digit

[Гост]

last 3 digit of [tex]\displaystyle 9^{9^{9^{9}}}[/tex]

[martin123456]

[tex]\varphi(1000)=400[/tex].
Нека [tex]9^{9^9}=400k+r[/tex], където [tex]0\le r<400[/tex].
Имаме [tex]9^{400} \equiv 1 \pmod{1000}\Rightarrow 9^{400k} \equiv 1 \pmod{1000}\Rightarrow 9^{9^{9^{9}}} \equiv 9^{400k+r}\equiv 9^r \pmod{1000}[/tex].
Значи трябва да намерим остатъка [tex]r[/tex] при деление на [tex]9^{9^9}[/tex] с [tex]400[/tex].
[tex]\varphi(400)=160[/tex].
Нека [tex]9^9=160k_1+r_1[/tex], където [tex]0\le r_1<160[/tex]. Тогава [tex]9^{9^{9}}\equiv 9^{160k_1+r_1}\equiv 9^{r_1} \pmod {400}[/tex].
С елка лесно можем да намерим [tex]r_1=9[/tex] и значи [tex]9^{9^{9} \equiv 9^9 \equiv 89 \pmod{400}[/tex].
Значи отговорът е [tex]89[/tex].

[Гост]

Thanks martin