Last two digits of n^n periodicity

Question

Let $f(n) = n^n\:[100]$ be the euclidean remainder of $n$ to the power of itself divided by 100, also known as the last two digits in decimal notation.

$n^n$ is a big number and time-consuming to compute.

Is it true that f is 100-periodic?

The following Python implementation provides two algorithms to compute the last two digits: a naive one and a recursive algorithm using multiplication rules. The goal is also to potentially improve the algorithm.

https://pyfiddle.io/fiddle/1456a98a-f771-475c-8eb1-610667588279

From running the simulation it looks like it follows the same pattern every 100. I also observed that :

$(n+100)^{n+100} = \sum\limits_{k=0}^{n+100} \binom{n+100}{k}n^{n+100-k}100^k = n^{n+100}\:[100] $

$100 = 2^2 5^2$ from the prime decomposition

$n^2 = n [2]$ and $n^5 = n [5]$ from Fermat's little theorem.

$n^{100} = (n+2i)^2(n+5j)^2 = n^4 + 10n^3j + 25n^2j^2 + 4n^3i + 40 n^2ij + 40 n^2i^2 + 40ni^2j\:[100]$ from expanding the terms.

Prove that $\forall n \in \mathbb{N}$, $(n+100)^{n+100} = n^n\:[100]$ or give a counter example.

Bonus question: What it the smallest period of $f$?

Answer 1

Another consideration is to use the multiplication in $\mathbb{Z}/100\mathbb{Z}$ to make the computation easier.

$\forall n \in \mathbb{N},\: \exists! p \in [0, 100[$ such that $n = p(n)\:[100]$.

$p$ is 100-periodic.

$f(n) = n^n = p(n)^n\:[100]$

So it suffices to show that the family of $f_p(n) = p^n\:[100]$ is 100-periodic for $p \in [0, 100[$.

$f_p(n+100) = p^np^{100} = f_p(n)p^{100}\:[100]$.

For example for the last case $n=2^i$ to study we show by recurrence on $i$ that $(2^i)^{100} = 76\:[100]$.

Observe in the same time that $(2^i)^{100} = 76$ is stable by multiplication by itself in in $Z/100Z$: $76^j = 76\:[100]$ for $j>0$.

And finally we show by recurrence that $f_{2^i}$ is also 100 periodic.

There might be an explanation that 2, 76 and 100 possess such properties together.

Is there a theorem to describe non trivial roots of $X^2=X\:[n]$ similar to Carmichael function ?

Answer 2

If you exempt $n=0$ (as $0^0$ is undefined), it is true.

Using the Chinese Remainder Theorem, it is sufficient to show that $n^n \equiv n^{n+100}$ mod $4$ and mod $25$.

Note that $\varphi(4) = 2$ and $\varphi(25) = 20$ are divisors of $100$, so using Euler's theorem this is true mod $4$ if $n$ and $2$ are coprime, and mod $25$ if $n$ and $5$ are coprime. On the other hand, if $n > 0$ is divisible by $2$, $n^n$ is divisible by $4$ and if $n > 0$ is divisible by $5$, $n^n$ is divisible by $25$.