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

$\begin{aligned} 961^{169^9} & \equiv 961^{\color{#3D99F6}169^9 \bmod \lambda(1000)} \text{ (mod 1000)} & \small \color{#3D99F6} \text{Since }\gcd(961,1000) = 1 \text{, Euler's theorem applies.} \\ & \equiv 961^{\color{#3D99F6}169^9 \bmod 100} \text{ (mod 1000)} & \small \color{#3D99F6} \text{Carmichael lambda function }\lambda (1000) = 100 \\ & \equiv 961^{\color{#D61F06}69^9 \bmod 100} \text{ (mod 1000)} & \small \color{#D61F06} \text{By modular inverse (see note)} \\ & \equiv 961^{\color{#D61F06}29} \\ & \equiv 31^{2\times 29} \text{ (mod 1000)} \\ & \equiv 31^{58} \text{ (mod 1000)} & \small \color{#3D99F6} \text{By modular inverse (see note)} \\ & \equiv \boxed{441} \end{aligned}$

---

Modular Inverse

Case 1: We note that $69^{10} \equiv (70-1)^{10} \equiv 1 \text{ (mod 100)}$ $\implies 69 \times 69^9 \equiv 1 \text{ (mod 100)}$ . Let $69^9 \bmod 100 = \overline{ab} = 10a+b$ , since $69 \equiv 69 \text{ (mod 100)}$ , we have

$\begin{aligned} 69(10a+b) & \equiv 1 \text{ (mod 100)} \\ 90a + 6{\color{#D61F06}9b} & \equiv {\color{#D61F06}1} \text{ (mod 100)} & \small \color{#D61F06} \text{For RHS to end with 1, }b \text{ must be 9 so that }9 \times 9 = 8\boxed{1} \\ {\color{#D61F06}9}0{\color{#D61F06}a} + 6{\color{#D61F06}2}1 & \equiv {\color{#D61F06}0}1 \text{ (mod 100)} & \small \color{#D61F06} \text{For tenth digit = 0, }a \text{ must be 2 so that }9 \times 2 + 2 = 2\boxed{0} \\ \implies 69^9 & \equiv \overline{ab} \equiv 29 \text{ (mod 100)} \end{aligned}$

Case 2: Similarly,

$\begin{aligned} 31^{60} & \equiv (30+1)^{60} \equiv (30\times 60+1) \equiv 801 \text{ (mod 1000)} \end{aligned}$

$\begin{aligned} \implies 31^231^{58} & \equiv 801 \text{ (mod 1000)} & \small \color{#3D99F6} \text{Let }31^{58} \bmod 1000 = \overline{pqr} \\ 961(100p+10q+r) & \equiv 801 \text{ (mod 1000)} \\ 100p+610q+96{\color{#3D99F6}1r} & \equiv 80{\color{#3D99F6}1} \text{ (mod 1000)} & \small \color{#3D99F6} \implies r = 1, \ \because 1 \times 1 = \boxed{1} \\ 100p+6{\color{#3D99F6}1}0{\color{#3D99F6}q}+9{\color{#3D99F6}6}1 & \equiv 8{\color{#3D99F6}0}1 \text{ (mod 1000)} & \small \color{#3D99F6} \implies q = 4, \ \because 1 \times 4 + 6 = 1\boxed{0} \\ 100p + 440 + 961 & \equiv 801 \text{ (mod 1000)} \\ {\color{#3D99F6}1}00{\color{#3D99F6}p}+{\color{#3D99F6}4}01 & \equiv {\color{#3D99F6}8}01 \text{ (mod 1000)} & \small \color{#3D99F6} \implies p = 4, \ \because 1 \times 4 + 4 = \boxed{8} \\ \implies 31^{58} & \equiv 441 \text{ (mod 1000)} \end{aligned}$