Sequence becomes constant modulo $n$

Question

Does the sequence $$a,a^a,a^{a^a},\cdots$$ is constant modulo $n$ from a certain rank ?

Where $a,n \in \mathbb{N}$

Using mathematica I am tempted to say yes but I how can I approach this ?

Any hint is appreciated.

Thank you in advance for your time.

Answer 1

This is true for all positive integers $a$ and $n$. By long induction on $n$:

The basic idea is that due to Euler's theorem your sequence is constant modulo $n$ from a certain point if the sequence of exponents $$ 1, a, a^a, \ldots $$ is constant modulo $\varphi(n)$ from a certain point. Since $\varphi(n)<n$, we can get this from the induction hypothesis.

There are two cases where this argument doesn't work. First $\varphi(n)<n$ is only true for $n\ge 2$, so we need to handle $n=1$ as a special case. But the conclusion is trivially true in that case, since all integers are congruent modulo 1.

The second problem is that Euler's theorem applies only when $a$ and $n$ are coprime, so we need another argument for when they are not. There are two subcases here:

If $n$ is a prime power $p^k$ and $a$ is not coprime to $n$, then $p$ divides $a$, so the sequence is eventually 0 modulo $n$ (because the exponents are strictly increasing because $a$ must be at least 2 when it has a prime factor).

On the other hand, if $n$ is not a prime power, then $n=mk$ for some coprime $m$ and $k$ that are both less than $n$. So the Chinese Remainder Theorem allows us to combine the induction hypotheses for $m$ and $k$.

---

It is not true when $a=0$ (except if $n=1$), because then the sequence is $0, 1, 0, 1, \ldots$.

It is not true when $n=0$ (except if $a=1$), because "congruent modulo 0" is either undefined or means simply "equal", depending on your temperament.

If we allow arbitrary real $a$ or $n$ greater than 1, then many counterexamples have to exist, due to measure-theoretic considerations. The details are a bit slippery, though.