A puzzle with powers and tetration mod n

We will need the following slight generalization of the totient theorem: $a^{k + \varphi(n)} \equiv a^k \bmod n$ for all $a$ provided that $k$ is at least as large as the largest exponent in the prime factorization of $n$.

It follows that

$$a^b \equiv a^{b \bmod 4} \bmod 5$$

provided that $b \ge 1$, and

$$b^c \equiv b^{c \bmod 2} \bmod 4$$

provided that $c \ge 2$ (where we need to take the remainder in $\{ 2, 3\}$). Finally,

$$c^d \equiv c \bmod 2$$

provided that $d \ge 1$. In summary,

$$a^{b^{c^d}} \equiv a^{b^c} \bmod 5$$

provided that $b \ge 1, c \ge 2, d \ge 1$. But this expression only depends on the value of $a \bmod 5, b \bmod 4, c \bmod 2$, so the sequence in question has eventual period dividing $20$, and computations of the first few terms suffices to show that the eventual period is an actual period. A similar argument works for $5$ replaced by any positive integer $m$ (but there is no guarantee that the eventual period is an actual period in this generality and I expect this to be false); we get that the eventual period divides $\text{lcm}(m, \varphi(m), \varphi(\varphi(m)), ...)$. And of course we can replace $\varphi(m)$ by the Carmichael function for larger $m$ to get better bounds.

For $k\ge 1$ we have

$$\begin{align*} {^{k+2}n}\bmod5&=(n\bmod5)^{^{k+1}n}\bmod5=(n\bmod5)^{^{k+1}n\bmod4}\bmod5\\ {^{k+1}n}\bmod4&=(n\bmod4)^{^kn}=\begin{cases} 0,&\text{if }n\bmod2=0\\ n\bmod4,&\text{otherwise}\;, \end{cases} \end{align*}$$

so

$${^{k+2}n}\bmod5=\begin{cases} (n\bmod5)^0=1,&\text{if }n\bmod2=0\\ (n\bmod5)^{n\bmod4},&\text{otherwise}\;. \end{cases}$$

In particular,

$${^nn}\bmod5=\begin{cases} (n\bmod5)^0,&\text{if }n\bmod2=0\\ (n\bmod5)^{n\bmod4},&\text{otherwise}\;. \end{cases}$$

for $n\ge3$, where $0^0\bmod5$ is understood to be $0$. Clearly the period starting at $n=3$ is a multiple of $20$; actual calculation shows that it is $20$, and that we cannot include the first two terms::

$$\begin{array}{r|c|c} n:&&&&&&&&&1&2\\ {^nn}\bmod5:&&&&&&&&&1&4\\ \hline n:&3&4&5&6&7&8&9&10&11&12\\ {^nn}\bmod5:&2&1&0&1&3&1&4&0&1&1\\ \hline n:&13&14&15&16&17&18&19&20&21&22&\\ {^nn}\bmod5:&3&1&0&1&2&1&4&0&1&1 \end{array}$$

(Added: And no, I’d not seen that Qiaochu had already answered the question until after I posted.)