0

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$?

Michel Hua
  • 103
  • The Carmichael number of $100$ is $20$, and $20\mid 100$, which supports your hypothesis of $100$-periodicity. However, you need to take care with the $n$'s which are divisible by either $2$ or $5$, since those aren't directly addressed by neither Fermat's little, Euler's theorem nor the Carmichael numbers. – Arthur Apr 12 '18 at 07:13
  • 2 and 5 are prime. One form of Fermat's little theorem states that if $p$ is prime $\forall n, n^p = n [p]$. (no further hypothesis on $n$ needed) – Michel Hua Apr 12 '18 at 13:46
  • But after using the Chinese remainder theorem on modulo $100$, you are really after modulo $4$ and $25$, not $2$ and $5$. – Arthur Apr 12 '18 at 13:59
  • To recapitulate, from Carmichael's theorem, $\lambda(100) = lcm(\lambda(4),\lambda(25)) = lcm(2, 20) = 20$, hence if $n$ and 100 are coprime, $n^{20} = 1 [100]$ and 20 is the lowest value possible.

    If so, $n^{100} = n^{20 \times 5} = 1:[100]$. Meaning that if 2 or 5 doesn't divide $n$ we get a recursive algorithm by first computing $k=n:[20]$, $m=n:[100]$ and then applying another algorithm that works fine for $m^k<n^n$, instead. So the problem reduces to studying the cases $m<100$, $k<20$.

     – Michel Hua Apr 12 '18 at 15:16
  • From the binomial formula above if 2 or 5 don't divide $n$, $(n+100)^{n+100} = n^n:[100]$ proving that $f$ is 100-periodic. We can generalize to every $10^k$ with $k>2$ to say that $f_k(n) = n^n:[10^k]$ is $10^k$ periodic. We still need to study these particular cases $2^i \times 5^j$ < 100 : 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 75, 80. I don't understand how Chinese Remainder Theorem helps at that point. – Michel Hua Apr 12 '18 at 15:35
  • So let's study $n=2^i \times 5^j$ for $i\geq0$ or $j\geq0$.

    $(i>0, j>0)$ We can at least observe that if 10 divides $n$, $n^n = 0 [100]$ proving the periodicity by absorbing multiplicity of the binomial formula above $f(n+100)=f(n)=0$.

    $(i=0, j>0), n=5^j$ If 5 divides $n$, we observe that if $n$ finishes by 5 than $f(n)$ always equals 25. See last expansion from Fermat little theorem.

     – Michel Hua Apr 12 '18 at 16:15
  • $n = 2^i$, bruteforcing we get, $f(2) = 4$, $f(4) = 56$, $f(8) = 16$, $f(16)=16$, $f(32)=76$, $f(64)=16$. I am stuck here. – Michel Hua Apr 12 '18 at 16:24

2 Answers2

0

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

Robert Israel
  • 448,999
  • There is absolutely no problem defining $0^0 = 1$. – Arthur Apr 12 '18 at 07:14
  • But if you do so, $0^0 \not\equiv 100^{100} \mod 100$. – Robert Israel Apr 12 '18 at 07:14
  • 1
    That is true. On the other hand, I would say that eventual periodicity is more natural to study than strict periodicity for this problem anyways, as the immediate generalization to modulo $1000$ has $2^2\not\equiv 1002^{1002}$. – Arthur Apr 12 '18 at 07:18
  • $\varphi(100) = \varphi(4) \varphi(25) = 2 \times 20 = 40$. So from Euler's theorem, if 100 and $n$ are coprime $n^{40} = 1 [100]$. Meaning that if 2 or 5 doesn't divide $n$ we get a recursive algorithm by first computing $k = n [40]$ and then applying another algorithm that works fine for $n^k < n^n$ instead. – Michel Hua Apr 12 '18 at 14:15
0

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 ?

Michel Hua
  • 103