# Eventually constant power tower

Given positive integers $a,m$, let $a_1=a,\ a_{n+1}=a^{a_n}, \forall n\in\mathbb Z_{\ge 1}$. Show that the sequence $(a_n)$ eventually becomes constant $\pmod m$.

A solution given is as follows:

Suppose that there is a counterexample. Then there is a counterexample for which $m$ is minimal. Trivially, $m\neq 1$.

Note that the sequence $\{ a^j\}_{j=0}^{\infty}$ eventually becomes periodic $\pmod m$; let the length of this period be $k$. Evidently, $1 \le k \le m-1$. Since $\{a_j\}_{j=2}^{\infty} = \{ a^{a_j}\}_{j=1}^{\infty}$ does not become constant mod $m$, it follows that $\{a_j \}_{j=1}^{\infty}$ does not become constant mod $k$. Thus $k$ is a smaller counterexample than $m$. Contradiction.

I do not understand how the bold part follows. Can someone help?

• I gave a proof of the same fact here - maybe it will help you. The last paragraph in particular seems to mirror what you have here. Commented Feb 22, 2015 at 22:20

The proof is noticing that the value of $a^{j}\pmod n$ is determined by knowing $j\pmod k$. This means that if $a_j$ is eventually constant mod $k$, then it follows that $a_{j+1}$ is eventually constant mod $n$, because its value, $a^{a_j}$ is determined by knowing $a_j$ mod $k$. The contrapositive of this is that if $a_j$ is not constant mod $n$, it cannot be constant mod $k$ either.