Finding last digit of $\,625703^{43898^{614961^{448629}}}\!\!$ using Euler's Theorem

Question

I'm a little bit stuck with this problem I hope you can help. I want to find the last digit of a power tower using Euler's theorem: \begin{align} q &= 10, \\ \varphi(q) &= 4, \\ \varphi(\varphi(q)) &= 2, \\\varphi(\varphi(\varphi(q))) &= 1. \end{align} \begin{align} 625703 ^{\displaystyle 43898 ^{\displaystyle 614961 ^{\displaystyle 448629}}} &\equiv (625703 \bmod 10)^{\displaystyle (43898 \bmod \varphi(10))^{\displaystyle (614961 \bmod \varphi(\varphi(10)))^{\displaystyle (448629 \bmod \varphi(\varphi(\varphi(10))))}}} \mod 10 \\ &\equiv 3^{\displaystyle 2^{\displaystyle 1^{\displaystyle 0}}} \mod 10 \\ &\equiv 3^{\displaystyle 2^{\displaystyle 1}} \mod 10 \\ &\equiv 3^{\displaystyle 2} \mod 10 \\ &\equiv 9 \mod 10 \end{align} According to this approach the last digit of the power tower must be 9. However, the right solution is 1 (see here) - what am I doing wrong?

This approach is based on the following two answers

computing ${{27^{27}}^{27}}^{27}\pmod {10}$

What's a general algorithm/technique to find the last digit of a nested exponential?

Answer 1

What am I doing wrong?

Euler's theorem assumes that the base and the modulus are relatively prime.

In your problem, that is not the case: $43898$ is not relatively prime to $4$.

In fact, $43898^n\equiv0\pmod4$ for $n\ge2$.

Can you solve it now?

Answer 2

\begin{align} 625703^{43898^{\scriptstyle614961^{\scriptstyle448629}}}\mkern-18mu\bmod 10&= (625703\bmod 10)^{43898^{\scriptstyle614961^{\scriptstyle448629}}\bmod\varphi(10)}\\ &= 3^{43898^{\scriptstyle614961^{\scriptstyle448629}}\mkern-12mu\bmod4}=3^{2^{\scriptstyle614961^{\scriptstyle448629}}\mkern-12mu\bmod4}=3^0. \end{align}

Answer 3

Hint: $ $ notice that: $\ n\ge 2\,\Rightarrow\, \color{#c00}{(2k)^n\bmod 4 \,\equiv\, 0}\ $ so by $ $ modular order reduction

$\!\!\bmod 10\!:\ 3^{\large \color{#c00}4}\equiv 1 \Rightarrow\ 3^{\large \color{}{(2k)^{\large n}}}\!\!\!\equiv 3^{\large \color{#c00}{(2k)^{\large n}\bmod 4}}\!\equiv 3^{\:\!\large\color{#c00} 0}\equiv 1,\ $ and

$\!\!\bmod 10\!:\ 625703\equiv 3\Rightarrow 625703^N\!\equiv 3^N\,$ by the Congruence Power Rule.

Remark $ $ The oversight is: Euler's theorem $\,a^{\phi(m)}\equiv 1\pmod{\!m}\,$ has hypothesis $\,\gcd(a,m)= 1\,$ so it does not apply to $\,(2k)^n\pmod{\! 4}.\,$ In such cases we can pull out the gcd of $\,a^N$ and $\,m\,$ using the mod Distributive Law, reducing to the coprime case where Euler applies, e.g. see here. Though it is overkill in this case, we could apply it above to factor out the common factor $2^2$ as follows

$$\quad\ \color{#0a0}{n\ge 2}\,\Rightarrow\,\color{#c00}{(2k)^{\large n}\!\bmod 4} \,=\, 2^2 (k^2 (2k)^{\large \color{#0a0}{n-2}}\!\bmod 1) \:\!=\:\! 2^2(0) \:\!=\:\! 0$$

Using this idea in your recursive algorithm then allows you to handle arbitrary power towers.