# The sequence defined by $a_1=c$ and $a_{i+1}=c^{a_i}$ is eventually constant modulo a positive integer $n$.

Show that for $$c \geq 1,$$ the sequence defined by $$a_1 = c$$ and $$a_{i+1} = c^{a_i}$$ for $$i \geq 1$$ is eventually constant when reduced modulo a positive integer $$n$$.

To prove this, I tried using the Chinese Remainder Theorem and reducing the sequence to the case where $$n$$ is a power of a prime $$p$$ that divides $$n$$. Then if $$p |c$$, the sequence is $$0$$ modulo $$n$$. But what about the case where $$p$$ does not divide $$c$$? Could you kindly suggest the next step?

• – lhf
Jun 3, 2020 at 12:12

We can do without the Chinese Remainder Theorem (and Euler's theorem). Assume $$c>1$$ and fix it.
Let $$b\geqslant 0$$ and $$d>0$$. Call a function $$f$$, defined on nonnegative integers, $$(b,d)$$-periodic if it has a period $$d$$ and a pre-period $$b$$; that is, if $$f(x+d)=f(x)$$ for any $$x\geqslant b$$ (we don't require minimality of $$b$$ or $$d$$ in any sense here).
For $$n>1$$, the map $$x\mapsto c^x\bmod n$$ is $$\big(b(n),d(n)\big)$$-periodic for some $$b(n),d(n)$$ with $$b(n)+d(n). Indeed, it takes at most $$n-1$$ values (check!), thus $$c^a\equiv c^b\pmod{n}$$ for some $$0\leqslant b; now we can take $$b(n)=b$$ and $$d(n)=a-b$$. For $$n=1$$, we put $$b(1)=0$$ and $$d(1)=1$$.
Now let $$f_0(x)=x$$ and $$f_{k+1}(x)=c^{f_k(x)}$$ for $$k,x\geqslant 0$$, so that our $$a_k=f_k(1)$$. Further, let $$d_0(n)=n,\quad d_{k+1}(n)=d_k\big(d(n)\big),\quad b_0(n)=0,\\b_{k+1}(n)=\min\left\{x\geqslant b_k\big(d(n)\big) : f_k(x)\geqslant b(n)\right\}.$$ Then, by induction on $$k$$, we see that $$x\mapsto f_k(x)\bmod n$$ is $$\big(b_k(n),d_k(n)\big)$$-periodic.
For a fixed $$n$$, as $$k$$ grows, $$d_k(n)$$ decreases strictly until it reaches $$1$$ (since $$d(n) if $$n>1$$), and $$b_k(n)$$ eventually reaches $$0$$ (here we use $$c>1$$, which makes $$f_k(0)$$ grow, so that $$f_k(x)\geqslant b(n)$$ holds for all $$x$$ if $$k$$ is large enough). Hence, $$x\mapsto f_j(x)\bmod n$$ is $$(0,1)$$-periodic (that is, constant) for some $$j$$. And then for $$k\geqslant j$$, $$f_k(1)=f_j\big(f_{k-j}(1)\big)$$ is constant modulo $$n$$.