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 at 19:42
  • That only happens when $x=3n$ with $n\in\mathbb{N}$ and there must be a factor of $9$ since at the base case $9\mid(3n)^{3n}$. But none of the other $x$s have $f(x\mid k)\pmod3=0$, so does that mean that $f(x\mid k)\pmod9\neq0,3,6$? – TheSimpliFire Mar 8 at 19:49
  • It's not even 'at the base case' per se, but yes, exactly. – Steven Stadnicki Mar 8 at 20:08
  • Thanks! I've put it in the post. – TheSimpliFire Mar 8 at 20:14
  • ..."has period 18..." - in $x$? - in $k$? – Gottfried Helms Mar 9 at 0:13
up vote 2 down vote accepted
+50

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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