Prove that $a_{n+1}=2^{a_n} $ is eventually constant $\mod r$. Let $(a_n)$ be a sequence such that $$a_{n+1}=2^{a_n}, \quad a_1=2$$
Prove that $\forall r\ge 1,\quad a_n\pmod r$ is eventually constant.
I took care of the case where $r=2^b$,
From the way $(a_n)$ is defined, we can see that $$\exists m\in \mathbb N, \text{ s.t. }\forall n\ge m, \quad a_n\equiv 0\pmod r$$
which is exactly what we want.
 A: We can recall Euler's theorem, a generalization of Fermat's little theorem which states that if $a$ is coprime to $r$ then
$$ a^{\phi(n)} \equiv 1 \mod n $$
Where $\phi(n)$ is Euler's Totient Function which counts the number of positive integers less than $n$ which are coprime to $n$
The significance of this is that the value $a_n \mod r$ can be evaluated as
$$ a_n \mod r \equiv 2^{a_{n-1}} \mod r $$
But we know that really
$$ 2^{a_{n-1}} \mod r  \equiv 2^{a_{n-1} \mod \phi(r)}  \mod r$$
And this can repeatedly applied to reveal
$$ a_n \mod r \equiv 2^{a_{n-1} \mod \phi(r)}  \mod r \equiv 2^{2^{a_{n-2} \mod \phi(\phi(r))} \mod \phi(r)} \mod r ... $$
Now the sequence $$\phi(r) \rightarrow \phi(\phi(r)) \rightarrow \phi(\phi(\phi(r))) ... $$ eventually tends to 1. A way to see that is to observe that by definition  $\phi(r) < r$ (unless r = 1) and $\phi(r)$ is always a positive natural number. So if we keep applying it we need to eventually hit 1. Lets say that the number of $\phi$'s it takes to reduce $r$ to 1 is $k$. So that $$\underbrace{\phi(\phi(...\phi(r)...))}_{\text{k  times}} = 1 $$ Usually we use notation $\phi^k(r)=1$ to indicate this.
Then we can consider $a_k$ which is $2^{2^{2^{...}}}$ a total of $k$ times. (This also has a name called 2 tetrated by k). We want to compare the value of $a_k \mod r$ to $a_{k+1} \mod r$.
$$ a_k \mod r \equiv 2^{2^{2^{{\mathstrut^{.^{.^{.^{2 \mod \phi^k(r)}}}}}} \mod \phi^2(r)} \mod \phi(r)} \mod r $$
And we know that $\phi^k(r) = 1$ so $2 \mod \phi^k(r) \equiv 0 \mod 1 $. So we can spell out that seemingly minor detail:
$$ a_k \mod r \equiv 2^{2^{2^{{\mathstrut^{.^{.^{.^{0 \mod 1}}}}}} \mod \phi^2(r)} \mod \phi(r)} \mod r $$
Lets now take a look at $a_{k+1}$. It's difference is exactly one power of 2 so it looks like:
$$ a_{k+1} \mod r \equiv 2^{2^{2^{{\mathstrut^{.^{.^{.^{2^{2 \mod \phi^{k+1}(r)} \mod \phi^k(r)}}}}}} \mod \phi^2(r)} \mod \phi(r)} \mod r $$
Now because $\phi^k(r) = 1$ we know that $\phi^{k+1}(r) = 1$ so we can write this as:
$$ a_{k+1} \mod r \equiv 2^{2^{2^{{\mathstrut^{.^{.^{.^{2^{2 \mod 1 } \mod \phi^k(r)}}}}}} \mod \phi^2(r)} \mod \phi(r)} \mod r $$
But $2 \mod 1 \equiv 0$ so we might as well write:
$$ a_{k+1} \mod r \equiv 2^{2^{2^{{\mathstrut^{.^{.^{.^{2^{0 \mod 1 } \mod \phi^k(r)}}}}}} \mod \phi^2(r)} \mod \phi(r)} \mod r $$
But $\phi^k(r)$ is also 1 so we can really right this as:
$$ a_{k+1} \mod r \equiv 2^{2^{2^{{\mathstrut^{.^{.^{.^{2^{0 \mod 1 } \mod 1}}}}}} \mod \phi^2(r)} \mod \phi(r)} \mod r $$
But any integer mod 1 is 0 so this entire expression can be removed and written as:
$$ a_{k+1} \mod r \equiv 2^{2^{2^{{\mathstrut^{.^{.^{.^{0 \mod 1}}}}}} \mod \phi^2(r)} \mod \phi(r)} \mod r $$
But now this is EXACTLY the same as $a_k$. So $a_{k+1} = a_k$. And now no matter how many times we keep on taking it the power of $2$ its just not going to change our value because the proof above can just be repeated again and again.
But $k$ is finite! So that means your sequence eventually will be $k$ values long and get stuck in this loop
A: We can use induction!
Suppose for all smaller $r$ the claim is true. That is, for all $k< r$, there is a number $n(k)$ such that $a_n\mod r$ is constant if $n\ge n(k)$. Now, from Euler's theorem, we know that if $a\equiv b\mod \phi(m)$ and $k$ and $m$ are coprime, we have $k^a$ and $k^b$ are congruent modulo $m$, where $\phi$ be the Euler's totient function.
Let $r=2^kl$ where $l$ is an odd number. Then, by induction, there exists some $n(\varphi(l))$ such that $a_n\mod l$ are same when $n\ge n(\varphi(l))$. Therefore, let $n(r)=\max (n(l)+1,k)$ we can see $a_n$ are same modulo $l$ if $n\ge n(l)+1$, and also $a_n$ are same modulo $2^k$ if $n\ge k$. Therefore we can find such $n(r)$.
