# Last digits don't change when exponentiating

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. Before doing so, I'll introduce a notation. Let's denote $$a_b=\underset{b\text{ times}}{\underbrace{a^{a^{a^{\cdots^a}}}}}$$ for $a,b\in\mathbb Z^+$.

Lemma 1. We have $2^k\mid 7_k-7_{k-1}$ for all $k\geq2$.

Proof. By induction. It's true for $k=2$, because $4\mid7^7-7$.

Assuming $7_k\equiv7_{k-1}\pmod{2^k}$, 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$

This gives us the divisibility by powers of $2$. For $10^k$ to be a divisor of $7_{k+2}-7_{k+1}$ we'll have to introduce powers of $5$.

Lemma 2. $7_{k+2}-7_{k+1}$ is divisible by $5^k$ for $k\geq1$.

Proof. We use the same technique. For $k=1$ this appears to be true. (You could check this with a computer, but it's a nice exercise to verify this by hand.)

Assuming $7_{k+2}\equiv7_{k+1}\pmod{5^k}$, we also have $7_{k+2}\equiv7_{k+1}\pmod{4\cdot5^k}$ (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+1})=4\cdot5^k$, we can conclude that $7_{k+3}\equiv7_{k+2}\pmod{5^{k+1}}$. $\square$

Combining both lemmas we obtain $10^k\mid7_{k+2}-7_{k+1}$. (In fact we have that $4\cdot10^k\mid7_{k+2}-7_{k+1}$.)

Note how your observations can be explained using these results. For example, we have $10^4\mid7_{6}-7_5$, and $10^5\mid7_7-7_6$. So certainly the last $4$ digits of $7_5,7_6$ and $7_7$ are the same.

You may ask yourself: "Can we improve this result? Is it possible that $10^k\mid7_{n+2}-7_{n+1}$ for $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.

First, note that it is equivalent to ask "is $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^p$, we need $7_{k+1}-7_k$ to be divisible by $\varphi(5^p)$ because $7$ is a primitive root modulo $5^p$. So certainly we need $5^{p-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}$.

I'll try to find out what happens if we replace $7$ by any number $m$ coprime or not coprime to $10$, but I don't have the time right now to do this. My guess is that most properties will reappear when $\gcd(m,10)=1$, but I'm not sure. (Certainly not of the minimality of $k$ we had because $7$ is a primitive root modulo $5^k$.)

-
This looks pretty good so far. Let me know what you come up with for other numbers used as the exponent. Thanks for the help. –  user3213784 Mar 6 '14 at 3:41

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.

-