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

Question

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.

Answer 1

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