Last digits of power towers $7$, $7^7$, $7^{7^7}$, $7^{7^{7^7}}$, ... don't change, and generalisation

While playing around with Wolfram Alpha, I noticed that the last four digits of $7^{7^{7^{7^7}}}, 7^{7^{7^{7^{7^7}}}},$ and $7^{7^{7^{7^{7^{7^7}}}}}$were all $2343$. In fact, the number of sevens did not seem to matter (so long as it exceeded five); the result was always $2343$. With further explanation, the last five digits appeared to remain unchanging with at least six sevens, and so on. When I replaced the sevens with other digits, the same effect appeared (even for digits not relatively prime to $10$, which somewhat surprised me).

My question is: can someone shed some light on why this is taking place? I have some [extremely] basic knowledge of [extremely] elementary number theory, and I've noticed that $7^{2343} \equiv 2343 \pmod{10^4}$ and similar results for other exponents and quantities of exponents, which explains why the pattern continues once it exists, but I haven't had much luck in proving that this will always work. I greatly appreciate any help anyone can provide me for explaining this interesting result. Thank you in advance.

Edit: I recently found that this question is strongly related to Problem 3 of the 1991 USAMO, the solution for which can be found here.

Before proving your observations, we need to know a few things; I'll present them as lemmas. Let's denote $$a_b=\underset{b\text{ times}}{\underbrace{a^{a^{a^{\cdots^a}}}}}$$ for $a,b\in\mathbb Z^+$. Here we agree to set $a_0 = 1$.

Lemma 1. $2^{k+1}\mid 7_{k+1}-7_k$ for $k\geq0$.

Proof. By induction. For $k=0$ this is trivial. Let $k\geq0$ and assume $7_k\equiv7_{k-1}\pmod{2^k}$. By Euler's theorem, we have $7^{7_k}\equiv7^{7_{k-1}}\pmod{2^{k+1}}$, because $7$ is relatively prime to $2^{k+1}$ and $\varphi(2^{k+1})=2^k$. This completes the induction. $\square$

Lemma 2. $5^{k-1}\mid 7_{k+1}-7_k$ for $k\geq1$.

Proof. We use the same technique. For $k=1$ this is trivial. Let $k\geq1$ and assume $7_{k+1}\equiv7_k\pmod{5^{k-1}}$. We also have $7_{k+1}\equiv7_k\pmod{4\cdot5^{k-1}}$ (For example by Lemma 1, but this is not very hard to verify without using the previous lemma.) Because of Euler's theorem and the fact that $\varphi(5^k)=4\cdot5^{k-1}$, we conclude that $7_{k+2}\equiv7_{k+1}\pmod{5^k}$. $\square$

Combining both lemmas, we obtain:

Theorem. $10^{k-1}\mid7_{k+1}-7_k$ for $k\geq1$, i.e., the last $k-1$ digits stay the same as soon as there are at least $k$ $7$'s.

Note how your observations can be explained using these results. For example, the last $4$ digits ($2343$) stay the same as soon as the power tower has at least $5$ $7$'s

Can we do better?

You may ask yourself: Can we improve this result? Is it possible that $10^k\mid7_{n+2}-7_{n+1}$ for some $n<k$? The answer is no, $k$ is the smallest such $n$. The reason for this is that $7$ is a primitive root modulo $5^k$ for all $k\geq1$. Let's see how the minimality of $k$ follows from this.

Note that it is sufficient to prove that $5^k$ the largest power of $5$ that divides $7_{k+2}-7_{k+1}$.

For $7_{k+2}-7_{k+1}$ to be divisible by $5^n$, we need $7_{k+1}-7_k$ to be divisible by $\varphi(5^n)$ because $7$ is a primitive root modulo $5^n$. So certainly we need $5^{n-1}\mid7_{k+1}-7_k$. This reasoning allows us to prove by induction that

Theorem. $5^k$ is the largest power of $5$ that divides $7_{k+2}-7_{k+1}$.

Consequently, $k$ is the smallest $n$ for which $10^k\mid7_{n+2}-7_{n+1}$.

Does this generalize to other numbers?

The question becomes: if $a,b>1$ are integers, does the sequence $a_n$ eventually become constant modulo $b$? If so, what is the least number of $a$'s starting from which the power tower stays constant modulo $b$?

We'll consider the case where $b$ is a prime power first, because the other cases reduce to this.

Note that in the example above, a crucial argument is that in order to 'transfer' congruence mod $5^k$, we needed congruence mod $\phi(5)$ for Euler's theorem to apply. In general, to transfer congruence mod $p^k$ we'll need to know something about congruence of power towers modulo all prime divisors of $p-1$, for which in turn we need congruence modulo the prime divisors of $\varphi$ of those prime divisors, etc... This is why we impose such a strong condition in the theorem below:

Theorem. Let $a>1$ be any integer, $p$ be prime and $k\geq1$. Suppose that, for some $n\in\Bbb N$, $\phi(q)\mid a_{n+1}-a_n$ for all primes $q\leq p$ (condition $\rm H$). If $p^m\mid a_{n+1}-a_n$ for some $m\geq0$, then $p^{k+m}\mid a_{n+k+1}-a_{n+k}$ for all $k\geq0$.

Note that we do allow that $p$ divides $a$, but such cases are trivial: if $p^m$ is the highest power of $p$ dividing $a_{n+1}-a_n$ (denoted $p^m\|a_{n+1}-a_n$), then $p^{m+1}\mid p^{m\cdot a_n}\|a_{n+2}-a_{n+1}$.

Proof. By induction on $p$. For $p=2$ there is no condition at all, and transferring congruence for growing $k$ is trivial if $a$ is even, and follows by Euler's theorem if $a$ is odd.

Let $p>2$. We want to proceed by induction on $k$ using Euler's theorem, so let $k\geq0$ and suppose $p^k\mid a_{n+k+1}-a_{n+k}$. We want to show that $\phi(p^{k+1})=(p-1)p^k\mid a_{n+k+1}-a_{n+k}$. Let $q^w$ be a prime power dividing $p-1$. By $\rm H$, $q^w\mid a_{n+1}-a_n$ and by induction on $p$ this implies $q^w\mid a_{n+k+1}-a_{n+k}$, so indeed $\phi(p^{k+1})\mid a_{n+k+1}-a_{n+k}$. Now suppose $q^m\mid a_{n+k+1}-a_{n+k}$. If $p\mid a$ then certainly $p^{m+1}\mid a_{n+k+2}-a_{n+k+1}$; if $p\nmid a$ this follows by Euler's theorem. $\square$

For example for odd $a$, if $2^m\mid a-1$ then $2^{m+k}\mid a_{k+1}-a_k$ for all $k\geq0$. If $a$ is even and $2^m\|a$, then $2^{m+k}\mid2^{m\cdot a_{k-1}}\|a_{k+1}-a_k$.

Note that the above theorem also gives a method to compute an upper bound $U_{p_n}$, independent of $a$, for the least $k$ for which $p^n\mid a_{m+1}-a_m$ for all $m\geq k$: just take the maximum of those upper bounds for all prime powers les then $p-1$, and add and add $n$. In fact, as explained in the next paragraph, it suffices to take the maximum over the prime powers dividing $p-1$. This gives the following values:

$\begin{array}{c|cc}\hline n\backslash p& 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67\\ \hline 1& 1 & 2 & 3 & 3 & 4 & 3 & 5 & 4 & 5 & 4 & 4 & 4 & 4 & 4 & 6 & 4 & 5 & 4 & 5\\ 2& 2 & 3 & 4 & 4 & 5 & 4 & 6 & 5 & 6 & \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 3& 3 & 4 & 5 & 5 & 6 & 5 & 7 & 6 & 7\\ 4&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&&&&&&U_{p^n} \end{array}$

For example, for $U_{19^2}$ we took the maximum of $U_2$ and $U_{3^2}$, which is $3$, and added $2$, which gives $5$. For $U_{67}$ we took the maximum of $U_2$, $U_3$ and $U_{11}$ and add $1$, which gives $5$.

As seen by the example in the beginning, this upper bound need not be tight for all $a$: for $p=5$ and $a=7$ we found $2$ as the least such $k$, whereas $U_5=3$.

Weakening $\rm H$ and tightness of ($a$-independent) upper bounds

A possible improvement, already incorporated above, of the upper bound lies in that the induction argument in the proof does not run through all primes $q<p$, but only the ones that appear in $\phi(p)$, $\phi(\phi(p))$, $\phi(\phi(\phi(p)))$, etc. If in the above procedure we only take the maximum of $U_{q^m}$ over all prime powers $q^m\mid p-1$, we automatically take into account divisors of $\phi(\phi(p))$, $\phi(\phi(\phi(p)))$, etc. as well, because of the recursive nature of the procedure. For example, in the calculation of $U_{67}$, a priori we would have take into account prime divisors of $\phi(3)$ and $\phi(11)$ as well, but those will not make the maximum any larger because their size is at most $U_3-1$ resp $U_{11}-1$.
Also the condition for Euler's theorem is in many cases too exigent; a necessary and sufficient condition is that the exponents are congruent modulo the order of the base mod the modulus, which is typically smaller than $\phi$ of the modulus. Let alone those cases where some prime $q$ divides $a$ - there we don't need any Euler-like condition at all, possibly discharging us of a whole tree of needed divisibility conditions. However, such improvements depend on the specific value of $a$, meaning that they should be investigated case by case.

It may be true that the $a$-independent upper bound (after the improvement with running only through prime divisors of $\phi(p)$, $\phi(\phi(p))$, $\phi(\phi(\phi(p)))$, $\ldots$) is not tight for all prime powers $p^n$, especially for $n>1$, because curious divisibility phenomena of the same flavor as Wieferich primes may occur, i.e.: for some $a$ and $p$, the smallest $k$ such that $p\mid a_{m+1}-a_m$ for all $m\geq k$ might be the same as the smallest $k$ such that $p^2\mid a_{m+1}-a_m$ for all $m\geq k$.

Further questions

If $p^m\mid a_{n+1}-a_n$, does this always imply $p^m\mid a_{n+2}-a_{n+1}$? (This would not cause an improvement of our upper bound, but could be interesting in view of the original question about constancy of the ending digits of power towers of growing size.)

Is the $a$-independent upper bound above tight for some $a$? For which prime powers do such $a$ exist?

Do Wieferich-like phenomena (see previous paragraph) ever occur?

This isn't a complete answer, but perhaps something that might be part of one.

Consider the equation $2^x \equiv x \pmod{100}$. The smallest positive solution is $x=36$. It also turns out that $36^{36} \equiv 36 \pmod{100}$. Thus if we have $2^{{36}^k} \pmod{100}$ it will reduce to $2^{36 * 36 * \dots * 36} \equiv (2^{36})^{36 * \dots * 36} \equiv 36^{36 * \dots * 36} \equiv 36 \pmod{100}$, so the residue will remain fixed no matter what power of 36 we raise 2 to. Something similar might be happening with your powers of 7 modulo 10000. 2343 is the smallest positive solution to $7^a \equiv a \pmod{10000}$. If we swap the roles it's also true that 7 is the smallest positive solution to $2343^a \equiv a \pmod{10000}$. I haven't thought about this long enough to know whether I should be surprised.

Let $(a,x)$ denote that $x$ is the smallest positive solution to $a^x \equiv x \pmod{10^d}$, where $d$ is the number of digits of $x$. I found the pairs (2,36), (3,87), (4,96), (5,25), (6,56), (7,43) [which contains the last two digits of your 2343 value], (8,56), and (9,89). Solutions to $a^a \equiv a \pmod{10^d}$, where $d$ is the number of digits of $a$, can be found here. The sequence itself is pretty interesting.