7
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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