Explain the solution to USAMO $1991/\rm P3$ Problem is as follows
Show that, for any fixed integer $n \geq 1$, the sequence
$2, 2^2, 2^{2^2}, ...\pmod n $
is eventually constant.
And the explanation was follows :
Define $i^{th}$ term of sequence to be $a_i$. Firstly assume $n$ is odd. Since $2^{\phi(n)} \equiv 1 \pmod n$. Then the thing that I dont understand is, hence if we can $a_k \equiv a_{k+1} \equiv a_{k+2} \equiv{  ...} \pmod {\phi(n)} $ for some $k$ then we would get,
$2^{a_k} \equiv 2^{a_{k+1}} \equiv { ...} \pmod n$ which is what we want.
Note : ${\phi(n)}$ is the number of integers less than $n$ and relatively prime to it.
What I don't get it is, by showing the result is true for ${\phi(n)}$, how can we  go back to showing it is true for $n$ as well?
Note : I just want an explanation, not proof.
 A: It is easy to verify that the statement is true for $n=1,2$. Now assume that the statement is true for all $m<n$. Since $\phi(n)<n$, the statement is true for $\phi(n)$ by induction hypothesis and hence, as you showed, true for $n$. Therefore by strong induction, you conclude that the statement is true for all $n\geq1$. Since the sequence, $a_k$ can be written as $a_{k+1}=2^{a_k}$ with $a_1=2$, true for $\phi(n)$ implies true for $n$. The situations when $n$ is odd or even can be handled, think a little. The crucial idea is to use strong induction.
A: For $n$ odd, $2$ is relatively prime to $n$, so the sequence of $a_i$ is some sequence in the set of numbers relatively prime to $n$, hence forms a set of residues modulo $n$ of size no greater than $\phi(n)$.  This is the content of Euler's theorem.  So the sequence
$$  2^{a_i} \pmod{n}, 2^{a_{i+1}} \pmod{n}, 2^{a_{i+2}} \pmod{n}, ...  $$
is termwise equal to the sequence
$$  2^{[a_i \pmod{\phi(n)}]} \pmod{n}, 2^{[a_{i+1} \pmod{\phi(n)}]} \pmod{n}, 2^{[a_{i+2} \pmod{\phi(n)}]} \pmod{n}, ... \text{,}  $$
where the square brackets pick a representative from the equivalence class given by the modulus (for instance, the least nonnegative representative of the residue class).
Also, this sequence of exponents is "one behind" the sequence term being defined.  That is,
$$  a_k \cong 2^{a_{k-1}}  \pmod{n}  \text{.}  $$
So the sequence made of the terms on the left-hand side of that equality is eventually constant if the sequence made of the exponents on the right-hand side are eventually all in the same residue class module $\phi(n)$.
Let's see an example.  Let's set $n = 7$ and see that $\phi(7) = 6$.
\begin{align*}
a_1 &\cong 2 \pmod{7} \cong 2^{[1 \pmod{6}]} \pmod{7}  \\
a_2 &\cong 4 \pmod{7} \cong 2^{[2 \pmod{6}]} \pmod{7}  \\
a_3 &\cong 16 \pmod{7} \cong 2^{[4 \pmod{6}]} \pmod{7}  \\
a_4 &\cong 65536 \pmod{7} \cong 2^{[16 \pmod{6}]} \cong 2^4 \pmod{7}  \\
a_5 &\cong 2^{65536} \pmod{7} \cong 2^{[65536 \pmod{6}]} \cong 2^4 \pmod{7} 
&\vdots
\end{align*}
Notice that at each step, $a_k \cong 2^{[a_{k-1} \pmod{\phi(n)}]} \pmod{n}$.  So if $\left( [a_{k-1} \pmod{\phi(n)}] \right)_k$ is eventually constant, then so is $(a_k \pmod{n})_k$.  Strong induction at step $n$ gives us the eventual constancy of $\left( [a_{k-1} \pmod{\phi(n)}] \right)_k$, because $\phi(n) < n$, and the above leverages that to constancy of $(a_k \pmod{n})_k$.
