# A puzzle with powers and tetration mod n

A friend recently asked me if I could solve these three problems:

(a) Prove that the sequence $1^1, 2^2, 3^3, \dots \pmod{3}$ in other words $\{n^n \pmod{3} \}$ is periodic, and find the length of the period.

(b) Prove that the sequence $1, 2^2, 3^{3^3},\dots \pmod{4}$ i.e. $\{\ ^nn \pmod{4}\}$ is periodic and find the length of the period.

(c) Prove that the sequence $1, 2^2, 3^{3^3},\dots \pmod{5}$ i.e. $\{\ ^nn \pmod{5}\}$ is periodic and find the length of the period.

The first two were not terribly difficult (but might be useful exercises in Fermat's little theorm), but the third one is causing me problems, since my methods are leading to rather a lot of individual cases, and I would be interested to see if anyone here can find a neater way to solve it.

(In (c), I have evaluated the first 15 terms, and not found a period yet - unless I have made a mistake.)

-

We will need the following slight generalization of the totient theorem: $a^{k + \varphi(n)} \equiv a^k \bmod n$ for all $a$ provided that $k$ is at least as large as the largest exponent in the prime factorization of $n$.

It follows that

$$a^b \equiv a^{b \bmod 4} \bmod 5$$

provided that $b \ge 1$, and

$$b^c \equiv b^{c \bmod 2} \bmod 4$$

provided that $c \ge 2$ (where we need to take the remainder in $\{ 2, 3\}$). Finally,

$$c^d \equiv c \bmod 2$$

provided that $d \ge 1$. In summary,

$$a^{b^{c^d}} \equiv a^{b^c} \bmod 5$$

provided that $b \ge 1, c \ge 2, d \ge 1$. But this expression only depends on the value of $a \bmod 5, b \bmod 4, c \bmod 2$, so the sequence in question has eventual period dividing $20$, and computations of the first few terms suffices to show that the eventual period is an actual period. A similar argument works for $5$ replaced by any positive integer $m$ (but there is no guarantee that the eventual period is an actual period in this generality and I expect this to be false); we get that the eventual period divides $\text{lcm}(m, \varphi(m), \varphi(\varphi(m)), ...)$. And of course we can replace $\varphi(m)$ by the Carmichael function for larger $m$ to get better bounds.

-
I think this is the sort of thing I was working towards, but had little hope of sorting out the details as clearly as you have. I had got as far as believing that I could prove the period for (c) had to be either a factor or a multiple of 20. +1 for now, while I think about it, and wonder if I can investigate your last statement about their being no guarantee. Many thanks! – Old John Aug 23 '12 at 23:07

For $k\ge 1$ we have

\begin{align*} {^{k+2}n}\bmod5&=(n\bmod5)^{^{k+1}n}\bmod5=(n\bmod5)^{^{k+1}n\bmod4}\bmod5\\ {^{k+1}n}\bmod4&=(n\bmod4)^{^kn}=\begin{cases} 0,&\text{if }n\bmod2=0\\ n\bmod4,&\text{otherwise}\;, \end{cases} \end{align*}

so

$${^{k+2}n}\bmod5=\begin{cases} (n\bmod5)^0=1,&\text{if }n\bmod2=0\\ (n\bmod5)^{n\bmod4},&\text{otherwise}\;. \end{cases}$$

In particular,

$${^nn}\bmod5=\begin{cases} (n\bmod5)^0,&\text{if }n\bmod2=0\\ (n\bmod5)^{n\bmod4},&\text{otherwise}\;. \end{cases}$$

for $n\ge3$, where $0^0\bmod5$ is understood to be $0$. Clearly the period starting at $n=3$ is a multiple of $20$; actual calculation shows that it is $20$, and that we cannot include the first two terms::

$$\begin{array}{r|c|c} n:&&&&&&&&&1&2\\ {^nn}\bmod5:&&&&&&&&&1&4\\ \hline n:&3&4&5&6&7&8&9&10&11&12\\ {^nn}\bmod5:&2&1&0&1&3&1&4&0&1&1\\ \hline n:&13&14&15&16&17&18&19&20&21&22&\\ {^nn}\bmod5:&3&1&0&1&2&1&4&0&1&1 \end{array}$$

Could you explain (for my poor old brain!) why $\ ^n3\equiv{\ ^{n\bmod3}3}\pmod5$? When I evaluated these things, I found myself having to find the residues mod 4, as the sequence $3^k \pmod{5}$ has period 4, doesn't it? – Old John Aug 23 '12 at 20:49
@OldJohn: But what you care about is the sequence $\langle ^n3\bmod5:n\in\Bbb Z^+\rangle=\langle 3,4,1,3,4,1,\dots\rangle$. – Brian M. Scott Aug 23 '12 at 20:56
Am I being very dim (not unknown!) - I thought $\ ^23 \equiv 3^3 \equiv 27 \equiv 2 \pmod{5}$? – Old John Aug 23 '12 at 21:07
@OldJohn: Oops! You’re right: I dropped a term. Of course it’s $\langle 3,2,4,1,\dots\rangle$. For $2$ it’s $\langle 2,4,1,\dots\rangle$, and for $4$ it’s $\langle 4,1,\dots\rangle$, so the actual period is $5\cdot4\cdot3=60$. I’ll revise the answer in just a moment. – Brian M. Scott Aug 23 '12 at 21:10