How to justify that the sequence $n^n\bmod 5$ is periodic?

Question

I'm asked in an exercise to give the possible reminders of $n^{n} \bmod 5$ in a congruency that is a good fit for n.

After doing so calculations I note that there seems to be a cycle of reminders each $20$ numbers.

This is also supported by the fact that the reminder is related with $r5(n)$ but also with $r4(n)$ (the way I calculate the reminder, for $n$ that are coprime with $5$, is $r5( r5(n)^{r4(n)} )$ where $rX$ is the remainder modulo X).

I'm confident that the answer is related with the cycle of reminders from $n = 0$ to $n = 20$. All the reminders will repeat for $n \geq 20$. But I'm not sure what would be a good justification of this. I guess the fact that $4 | 20$ and $5 | 20$, it's the least common multiple, has something to do with this.

Answer 1

You're right about $20$ being the least common multiple of $4$ and $5$ being relevant. Using Fermat's Little Theorem, we have $$a^5 \equiv a \ \mathbf{mod} \ 5,$$ for all $a$. So, if $n > 1$, we have \begin{align*} (n + 20)^{n + 20} &\equiv (n + 20)^{n-1} (n + 20)^{21} \\ &\equiv (n + 20)^{n-1} (n + 20) \\ &\equiv (n + 20)^n \\ &\equiv n^n. \end{align*} On the other hand, if $n = 1$, then $$21^{21} \equiv 1^{21} \equiv 1.$$ In any case, we get what we want.

Answer 2

Note that your expression $r5(n)^{r4(n)}$ only depends on $n\bmod 5$ and $n\bmod 4$. The pair of values of these repeat every $20$ as shown in the Chinese Remainder Theorem.