1

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.

Arnaud Mortier
  • 27,276
hhaamm
  • 187
  • 1
    You can use Fermat's little theorem to compute the remainder of $(n+20)^{n+20}=n^{n+20}+\text{ a multiple of }5$. And then the remainder of $n^{n+20}=n^n(n^5)^4$. Using Fermat's little theorem conclude that the remainder of $(n^5)^4$ is $1$ if $n$ is not divisible by $5$ or $0$ when it is. In both cases $(n+20)^{n+20}$ ends up with the same remainder as $n^n$. –  Jul 24 '18 at 02:44

2 Answers2

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.

Theo Bendit
  • 50,900
1

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.

Ross Millikan
  • 374,822