7
$\begingroup$

Going through some random numbers, I have found that $n^n\mod10$ repeats every $20$ terms, and it more or less is as follows.

$$1^1\equiv1\pmod{10}$$

$$2^2\equiv4\pmod{10}$$

and so on. The sequence I found was $1,4,7,6,5,6,3,6,9,0,1,6,3,6,5,6,7,4,9,0,\dots$ After that, it appears to repeat.

In modular $3$: $1,1,0,1,2,0,\dots$ and it appears to repeat as well.

Is there an explanation for this? And is there anything provable about this?

Naturally, I don't mind numerical results that disprove my statement, but even so, it is interesting that the numbers appear to repeat.

$\endgroup$
8
$\begingroup$

This is not quite true, but it's very close to being true. In particular, the truth of this hinges on the following statement:

The sequence $1,n,n^2,n^3,\ldots$ is eventually periodic mod any $m$.

More strongly, one can find that the period of this sequence will always divide $\lambda(m)$ where $\lambda$ is the Carmichael function, which is the smallest $k$ such that $n^k\equiv 1\pmod m$ for any $n$ coprime to $m$. This is almost tautological - the only step of interest is that if $n$ isn't coprime to $m$, one can take the largest divisor $m'$ of $m$ such that $m'$ and $n$ are coprime, and see that the period of the sequence divides $\lambda(m')$ which divides $\lambda(m)$.

In particular, this tells us that the sequence $n^n$ mod $m$ will be eventually periodic with a period of $P=\operatorname{lcm}(m,\lambda(m))$. We may prove this since we can first get that, since $m$ divides $P$, we have $$n^{n}\equiv (n+P)^n\pmod m$$ and then since, for large enough $n$ we have that $x^n=x^{n+\lambda(m)}$ for any $x$, we get that $x^n=x^{n+P}$ since $\lambda(m)$ divides $P$, so: $$n^n\equiv (n+P)^{n+P}\pmod m$$ as desired. It seems reasonable that $P$ is the fundamental period of the sequence $n^n$, but I haven't managed to prove this yet. (It is, however, possible to see that the lcm of the fundamental period and $m$ is $P$, but this doesn't quite suffice).

In particular, the quantity $\operatorname{lcm}(m,\lambda(m))$ is $20$ when $m=10$ and is $6$ when $m=3$. However, when $m=5$, this quantity is $20$ and the sequence is only periodic with period $20$. The first $40$ terms are as follows: \begin{align*}&1, 4, 2, 1, 0, 1, 3, 1, 4, 0, 1, 1, 3, 1, 0, 1, 2, 4, 4, 0,\\ &1, 4, 2, 1, 0, 1, 3, 1, 4, 0, 1, 1, 3, 1, 0, 1, 2, 4, 4, 0,\ldots\end{align*}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wonderful answer! $\endgroup$ – Simply Beautiful Art Jun 14 '16 at 20:28
  • $\begingroup$ For the record, I'd also point out that this same logic extends to tetration ("power towers"). Using this technique to find the period, you'll discover that fairly quickly the period of a mod on a tetrated value becomes constant---even if the tetration tower is infinitely high. $\endgroup$ – Trevor Aug 26 '19 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.