Last digits of ${square}^{{square}^{square}}$

Relevant wiki: Euler's Theorem

Let $N = 1444^{144^4}$ , we need to find $N \bmod 10000$ . Since 1444 and 10000 are not coprime integers, we shall consider the factors $2^4 = 16$ and $5^4 = 625$ of 10000 separately using Chinese remainder theorem .

Consider factor 16: $N \equiv 0 \text{ (mod 16)}$ .

Consider factor 625:

$\begin{aligned} N & \equiv 1444^{\color{#3D99F6} 144^4 \bmod \phi (625)} \text{ (mod 625)} & \small \color{#3D99F6} \text{Since }\gcd(144, 625) = 1 \text{, Euler's theorem applies.} \\ & \equiv 1444^{\color{#3D99F6} 144^4 \bmod 500} \text{ (mod 625)} & \small \color{#3D99F6} \text{Euler's totient function }\phi(625) = 500 \\ & \equiv 1444^{\color{#3D99F6}196} \text{ (mod 625)} & \small \color{#3D99F6} \text{By modulo inverse (see note)} \\ & \equiv (1000+444)^{5\times 39+1} \text{ (mod 625)} \\ & \equiv 444^{195}(1444) \text{ (mod 625)} \\ & \equiv 4^{195}111^{195}(194) \text{ (mod 625)} \\ & \equiv (5-1)^{125+70}(110+1)^{125+70}(194) \text{ (mod 625)} \\ & \equiv (-1)4^{70}111^{70}(194) \text{ (mod 625)} \\ & \equiv (5-1)^{70}(110+1)^{70}(431) \text{ (mod 625)} \\ & \equiv \left(\frac {70(69)5^2}2 - 70(5) + 1\right) \left(\frac {70(69)110^2}2 + 70(110) + 1\right)(431) \text{ (mod 625)} \\ & \equiv (26)(451)(431) \text{ (mod 625)} \\ & = 156 \text{ (mod 625)} \end{aligned}$

Therefore,

$\begin{aligned} N & \equiv 625n + 156 & \small \color{#3D99F6} \text{where }n \in \mathbb Z \\ \implies 625n + 156 & \equiv 0 \text{ (mod 16)} \\ n + 12 & \equiv 0 \text{ (mod 16)} \\ n & \equiv 4 \\ \implies N & \equiv 625(4) + 156 \text{ (mod 10000)} \\ & \equiv \boxed{2656} \text{ (mod 10000)} \end{aligned}$

---

Note: $\begin{aligned} 144^5 & \equiv (100+44)^5 \equiv 44^5 \equiv (45-1)^5 \equiv 5\times 45 - 1 \equiv 224 \text{ (mod 500)} \end{aligned}$

$\begin{aligned} \implies 144 \times \color{#3D99F6}144^4 & \equiv 224 \text{ (mod 500)} & \small \color{#3D99F6} \text{Let }144^4 \equiv \overline{abc} \equiv 100a+10b+c \text{ (mod 500)} \\ 144 \times \color{#3D99F6}\overline{abc} & \equiv {\color{#D61F06}224} \text{ (mod 500)} \\ 144 \times \overline{ab6} & \equiv 1440\overline{ab} + 86{\color{#D61F06}4} \text{ (mod 500)} \\ 144 \times \overline{a96} & \equiv 14400a + 138{\color{#D61F06}24} \text{ (mod 500)} \\ 144 \times 196 & \equiv 28{\color{#D61F06}224} \equiv 224 \text{ (mod 500)} \\ \implies 144^4 & \equiv 196 \text{ (mod 500)} \end{aligned}$

The answer $x$ can be computed using $x \equiv 1444^{144^{4}} \pmod{10000}$

A simple solution is just to consider $144^4$ as $3^{8} \times 2^{16}$ so we can just square $1444$ sixteen times and cube it eight times performing modulo 10000 in each step. Modulo 10000 by hand is easy because it's just truncation. It will require $16 + 2 \times 8 = 32$ 4-digit multiplications. We can apply Euler's Theorem and Chinese Remainder Theorem to reduce the exponent, but it becomes a much more complicated procedure.

$x \equiv 1444^{3^{8} \times 2^{16}} \pmod{10000}$

$x \equiv 5136^{3^{8} \times 2^{15}} \pmod{10000}$

$x \equiv 8496^{3^{8} \times 2^{14}} \pmod{10000}$

$x \equiv 2016^{3^{8} \times 2^{13}} \pmod{10000}$

$x \equiv 4256^{3^{8} \times 2^{12}} \pmod{10000}$

$x \equiv 3536^{3^{8} \times 2^{11}} \pmod{10000}$

$x \equiv 3296^{3^{8} \times 2^{10}} \pmod{10000}$

$x \equiv 3616^{3^{8} \times 2^{9}} \pmod{10000}$

$x \equiv 4345^{3^{8} \times 2^{8}} \pmod{10000}$

$x \equiv 7936^{3^{8} \times 2^{7}} \pmod{10000}$

$x \equiv 96^{3^{8} \times 2^{6}} \pmod{10000}$

$x \equiv 9216^{3^{8} \times 2^{5}} \pmod{10000}$

$x \equiv 4656^{3^{8} \times 2^{4}} \pmod{10000}$

$x \equiv 8336^{3^{8} \times 2^{3}} \pmod{10000}$

$x \equiv 8896^{3^{8} \times 2^{2}} \pmod{10000}$

$x \equiv 8816^{3^{8} \times 2^{1}} \pmod{10000}$

$x \equiv 1856^{3^{8}} \pmod{10000}$

Now we cube 8 times.

$x \equiv 16^{3^{7}} \pmod{10000}$

$x \equiv 4096^{3^{6}} \pmod{10000}$

$x \equiv 6736^{3^{5}} \pmod{10000}$

$x \equiv 6256^{3^{4}} \pmod{10000}$

$x \equiv 5216^{3^{3}} \pmod{10000}$

$x \equiv 7696^{3^{2}} \pmod{10000}$

$x \equiv 9536^{3^{1}} \pmod{10000}$

$x \equiv 2656 \pmod{10000}$