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?


1 Answer 1


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)<n$. Indeed, it takes at most $n-1$ values (check!), thus $c^a\equiv c^b\pmod{n}$ for some $0\leqslant b<a<n$; 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)<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$.

For a much deeper analysis, look for this article.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .