# 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?) Mar 8, 2018 at 19:42
• It's not even 'at the base case' per se, but yes, exactly. Mar 8, 2018 at 20:08
• ..."has period 18..." - in $x$? - in $k$? Mar 9, 2018 at 0:13
• @GottfriedHelms In $x$. So for example $$20^{20^{20}}\equiv2^{2^{2}}\pmod9$$ Mar 9, 2018 at 6:06

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