# Is it true that $\underbrace{x^{x^{x^{.^{.^{.^x}}}}}}_{k\,\text{times}}\pmod9$ has period $18$ and can never take the values $3$ and $6$?

Is it true that the arithmetical function $f:\mathbb{N}\setminus\{1\}\rightarrow \mathbb{Z}_9$ given by $$f(x\mid k)=\underbrace{x^{x^{x^{.^{.^{.^x}}}}}}_{k\,\text{times}}\pmod9$$

• has period $18$

• can never take the values $3$ and $6$?

Note that $k\in\mathbb{N}\setminus\{1\}$.

Attempt

For $k=2$, we have $$f(x\mid2)=x^x\pmod9$$ Repetitively using FLT and Euler's Theorem gives the sequence $$4,0,4,2,0,7,1,0,1,5,0,4,7,0,7,8,0,1,\color{red}{4,0,4,\cdots}$$ corresponding to each $x=2,3,4,\cdots$.

We see two things: the sequence in black has length $18$ which acts as a repeating unit, and $3$ and $6$ don't appear in it.

One can try this for $f(x\mid3)$ and the results are the same.

I think induction looks possible but I do not know how to show this step:

• Given that $f(x\mid k)$ is true, $f(x\mid k+1)$ is also true.

I suspect that there will be other slightly faster methods as well.

EDIT

With the help of @StevenStadnicki, I have managed to prove the second part.

If we consider $f(x\mid k)\pmod3$, then it equals $0$ only if $x=3n$ where $n$ is a natural number, which in turn means that $f(3n\mid k)=0\pmod9$ as $9\mid(3n)^{3n}$ - case when $k=2$.

However, for other $x$, $$f(x\mid k)\neq0\pmod3\implies f(x\mid k)\neq0,3,6\pmod9$$ Q.E.D.

• You can easily show the 'can never take the values 3 and 6'. Consider $f(x\mid k)\bmod 3$ and show that if it's $0\bmod 3$, then it must be a multiple of $9$. (Hint: what constraints does $x$ have in that case?) – Steven Stadnicki Mar 8 '18 at 19:42
• It's not even 'at the base case' per se, but yes, exactly. – Steven Stadnicki Mar 8 '18 at 20:08
• ..."has period 18..." - in $x$? - in $k$? – Gottfried Helms Mar 9 '18 at 0:13
• @GottfriedHelms In $x$. So for example $$20^{20^{20}}\equiv2^{2^{2}}\pmod9$$ – TheSimpliFire Mar 9 '18 at 6:06

## 1 Answer

$\def\tet{\mathbin{↑↑}}$First, note that if $(a_1, m) = 1$, $a_1 \equiv a_2 \pmod{m}$, $b_1 \equiv b_2 \pmod{φ(m)}$, then $a_1^{b_1} \equiv a_2^{b_2} \pmod{m}$.

Case 1: $k = 2$. For any $x \in \mathbb{N}_+$, if $3 \mid x$, then$$(x + 18)^{x + 18} \equiv 0 \equiv x^x \pmod{9}.$$ Otherwise $(3, x) = 1$, and$$x + 18 \equiv x \pmod{6}, \quad x + 18 \equiv x \pmod{9},$$ which implies$$x^x \equiv (x + 18)^{x + 18} \pmod{9}.$$

Case 2: $k \geqslant 3$. For any $x \in \mathbb{N}_+$, if $3 \mid x$, then$$(x + 18) \tet (x + 18) \equiv 0 \equiv x \tet x \pmod{9}.$$ Otherwise, $(3, x) = 1$. Now, because $x \tet (k - 2) \equiv x \pmod{2}$, then$$(x + 18) \tet (k - 2) \equiv x + 18 \equiv x \equiv x \tet (k - 2) \pmod{2}.$$ Also, $x + 18 \equiv x \pmod{3}$, thus$$(x + 18) \tet (k - 1) = (x + 18)^{(x + 18) \tet (k - 2)} \equiv x^{x \tet (k - 2)} = x \tet (k - 1) \pmod{3}.$$ Because$$(x + 18) \tet (k - 1) \equiv x + 18 \equiv x \equiv x \tet (k - 1) \pmod{2},$$ then$$(x + 18) \tet (k - 1) \equiv x \tet (k - 1) \pmod{6}.$$ Since $x + 18 \equiv x \pmod{9}$, then$$(x + 18) \tet k = (x + 18)^{(x + 18) \tet (k - 1)} \equiv x^{x \tet (k - 1)} = x \tet k \pmod{9}.$$