# 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. – Hw Chu Sep 27 '18 at 22:46
• i need to do this by hand ':( @Hw Chu – emonHR Sep 28 '18 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 – emonHR Sep 29 '18 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. – Fabio Lucchini Sep 29 '18 at 19:13
• The tower of powers of your question can be defined recursively by mean of the function $\psi$. – Fabio Lucchini Sep 29 '18 at 19:17
• Thank you for again help me @Fabio Lucchini :) – emonHR Sep 30 '18 at 8:24