Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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$.)

share|improve this answer
    
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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.