Application of Euler's totient function to find last digits

Q:what are the last five digits of the number $$2018^{2017^{.^{.^{.^{2^{1}}}}}}$$.
My Approach:I know how to find the last two digits of $$N=2018^{2017^{k}}$$ by
$$N=2018^{2017^{k}\pmod{\phi(25)}}\pmod {25}\equiv 2018^{2017^{2016^b\pmod{8}}\pmod{20}}\pmod {25}\equiv 2018^{2017^0\pmod{20}}\pmod {25}\equiv 2018^1\pmod {25}\equiv18\pmod{25}$$
Again,
$$N=18+25n\equiv0\pmod4$$ Suppose n is an arbitrary integer.Solving it to find n.
$$18+25n\equiv0\pmod4\Rightarrow n=2\pmod4$$ Therefore, we have:
$$N=25(2)+18\pmod{100}\equiv68\pmod{100}$$ By chinese remainder theorem.
but now I couldn't think of how to go with it by $$\pmod{100000}$$.Any hints or solution will be appreciated.

• I got the answer 36768 by running a program. Sadly in my opinion it does not seem too hopeful to have an algorithm that can be done by hand which is significantly faster than your method for computing mod 100. Commented Sep 27, 2018 at 22:46
• i need to do this by hand ':( @Hw Chu Commented Sep 28, 2018 at 6:47

Let $\psi(0)=1$ and $\psi (n)=n^{\psi (n-1)}$. We have to find $\psi (2018)\pmod {10^5}$.

Clearly $\psi (2015)\equiv 0\pmod {5^2}$ and $\psi (2015)\equiv 1\pmod 4$, from which $\psi (2015)\equiv 25\pmod {4\cdot 5^2}$, by chinese remainder theorem.

Consequently, $\psi (2016)\equiv 2016^{25}\equiv 16^{25}\equiv 2^{100}\equiv 1\pmod {5^3}$. On the other hand, $\psi (2016)\equiv 0\pmod 4$, from which $\psi (2016)\equiv 376\pmod {4\cdot 5^3}$, by chinese remainder theorem.

Consequently, $\psi (2017)\equiv 2017^{376}\equiv 142^{376}\equiv 406\pmod {5^4}$. On the other hand $\psi (2017)\equiv 1\pmod 4$, from which $\psi(2017)\equiv 2281\pmod {4\cdot 5^4}$, by chinese remainder theorem.

Consequently, $\psi (2018)\equiv 2018^{2281}\equiv 11768\pmod {5^5}$. On the other hand, $\psi (2018)\equiv 0\pmod {2^5}$, from which $\psi (2018)\equiv 36768\pmod {10^5}$, by chinese remainder theorem.

• first of all thank you very much for your clear explanation.but i didn't see $\psi (n)=n^{\psi (n-1)}$ this formula before.In your 4th line $\psi (2016)=2016^{\psi(2016-1)}$ and $\psi(2015)=1440$ then how you get $\psi (2016)\equiv 2016^{25}\equiv 16^{25}\equiv 2^{100}\equiv 1\pmod {5^3}$ ?? Can you explain me these thing please. And again thank you very much @Fabio Lucchini Commented Sep 29, 2018 at 16:29
• $\psi(2016)\equiv 2016^{25}\pmod{5^3}$ follows by application of Euler totient function since $\phi(5^3)=4\cdot 5^2$ and $\psi(2015)\equiv 25\pmod{4\cdot 5^2}$. Similarly, for others lines below. Commented Sep 29, 2018 at 19:13
• The tower of powers of your question can be defined recursively by mean of the function $\psi$. Commented Sep 29, 2018 at 19:17
• Thank you for again help me @Fabio Lucchini :) Commented Sep 30, 2018 at 8:24