A puzzle with powers and tetration mod n A friend recently asked me if I could solve these three problems:
(a) Prove that the sequence $ 1^1, 2^2, 3^3, \dots \pmod{3}$ in other words  $\{n^n \pmod{3} \}$ is periodic, and find the length of the period.
(b) Prove that the sequence $1, 2^2, 3^{3^3},\dots \pmod{4}$ i.e. $\{\ ^nn \pmod{4}\}$ is periodic and find the length of the period.
(c) Prove that the sequence $1, 2^2, 3^{3^3},\dots \pmod{5}$ i.e. $\{\ ^nn \pmod{5}\}$ is periodic and find the length of the period.
The first two were not terribly difficult (but might be useful exercises in Fermat's little theorm), but the third one is causing me problems, since my methods are leading to rather a lot of 
individual cases, and I would be interested to see if anyone here can find a neater way to solve it.
(In (c), I have evaluated the first 15 terms, and not found a period yet - unless I have made a mistake.)

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.)
