What is the ten's digit of $7^{7^{7^{7^7}}}$

Question

What is the ten's digit of $\zeta=7^{7^{7^{7^7}}}$. I got this question while doing binomial theorem. I think that $7^4=2401$ and we only need $\zeta\pmod{100}$. All I could think of is already presented (thought it is nothing actually), would you help?

Answer 1

Note that $$7^2=49,\ 7^3=343,\ 7^4=2401,\ 7^5=168\color{red}{07}.$$

So, all we need is to find $7^{7^{7^{7}}}$ in mod $4$.

Now $$7^{7^{7^{7}}}\equiv (-1)^{7^{7^{7}}}\equiv -1\equiv 3\pmod 4.$$ Hence, the answer we want is the same as the ten's digit of $343$, i.e. $\color{red}{4}$.

Answer 2

Euler's theorem: $(a,n)=1\,\Rightarrow\, a^{\phi(n)}\equiv 1\pmod {\!n}$, where $\phi(n)$ denotes Euler's totient function, which is a function outputting the amount of positive integers less than $n$ that are coprime to $n$.

So, e.g., $\phi (10)=4$, because $1,3,7,9$ (four positive integers) are coprime to $10$ and $2,4,5,6,8$ are not.

It can be proved that (there is a unique representation $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ with $p_i$ prime (because of Fundamental Theorem of Arithmetic))

$$\phi(n)=\phi(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k})=(p^\alpha_1-p^{\alpha_1-1})(p_2^{\alpha_2}-p_2^{\alpha_2-1})\cdots(p_k^{\alpha_k}-p_k^{\alpha_k-1})$$

So, e.g., $\phi(2700)=\phi(2^23^35^2)=(4-2)(27-9)(25-5)=2\cdot 18\cdot 20=720$.

$\phi(n)$ and other numbers $m$ such that $a^m\equiv 1\pmod{n}$ can be used to reduce exponents ($a^E\equiv a^{E\!\pmod {\! m}}\!\pmod {\!n}$), as will be shown later in this answer.

Your problem isn't easily approachable using Euler's theorem (using it to reduce the exponent won't be as simple, since it is too large and we can find smaller such numbers - $4$ in this example), but it is an exception. The best strategy for this kind of problems with exponentiation ($a^E\!\pmod {\!n}$) is finding the order (I'll explain), denoted $\text{ord}_n a$, of $a$ modulo $n$, or a multiple of it, and this is why finding and using $\phi(n), \lambda(n)$ (I'll introduce you to it later in the answer) is useful.

The multiplicative order, denoted $\text{ord}_n a$, of $a$ modulo $n$ is the least positive $s$ such that $a^s\equiv 1\!\pmod {\!p}$.

So, in our example, $\text{ord}_{100} 7=4$, since $7^4\equiv 2401\equiv 1\!\pmod {\! 100}$ while $7^1,7^2,7^3\not\equiv 1\!\pmod {\!100}$.

Then any $t$ such that $a^t\equiv 1\!\pmod{\!n}$ will be divisible by $s$, i.e. $t=sl$ for some $l\in\mathbb Z$. Notice that $\phi(n),\lambda(n)$ are instances of such $t$ and so they're multiples of the orders.

The reason why finding orders or multiples of them (like $\phi(n),\lambda(n)$) is important in this kind of problems is because it lets us reduce the exponent. E.g., in the case of this problem, $$7^{7^{7^{\ldots}}}\equiv 7^{7^{7^{\ldots}}\!\pmod{\!4}}\equiv 7^{(-1)^{7^{\ldots}}\!\pmod {\!4}}\equiv 7^{-1\!\pmod {\!4}}\equiv 7^3\equiv 343\!\!\!\pmod{\!100}$$

The reason why we could reduce the exponent modulo $4$ is because $7^4\equiv 1\!\pmod{\!100}$, so, e.g., $7^{13}\equiv 7^{4+4+4+1}\equiv 7^47^47^47^1\equiv 1\cdot 1\cdot 1\cdot 7\equiv 7\!\pmod {\!100}$. The reason I said "Your problem isn't easily approachable using Euler's theorem" is because $\phi(100)=40$ is too large compared to $4$. Mathlove's answer uses the same idea.

Carmichael function, denoted $\lambda (n)$, is defined as the smallest $m$ such that $(a,n)=1\,\Rightarrow\, a^m\equiv 1\!\pmod{\!n}$.

Notice how $\phi(n)$ satisfies the conditions, except for the 'smallest'. So $\lambda(n)$ is just a smaller version of $\phi(n)$ (we have $\lambda(n)\le \phi(n)$).

It can be proved that $$\lambda(n)=\begin{cases}\phi(n),\ \ \ n=2,4,p_{\text{odd}}^k\\\frac{1}{2}\phi(n),\ \ \ n=2^k,k\ge 3\\\text{lcm}(\lambda(p_1^{\alpha_1}),\lambda(p_2^{\alpha_2}),\ldots,\lambda(p_k^{\alpha_k}))\ \ \ \text{ otherwise}\end{cases}$$

So, e.g., (if $k\ge 4$)

$$\lambda(10^k)=\text{lcm}(\lambda(2^k),\lambda(5^k))=\text{lcm}(2^{k-2},4\cdot 5^{k-1})=2^{k-2}5^{k-1}$$

while $\phi(10^k)=(2^k-2^{k-1})(5^{k}-5^{k-1})=2^{k-1}\cdot 4\cdot 5^{k-1}=2^{k+1}5^{k-1}$.

Notice how for $k\ge 4$ we have $\lambda(10^k)=\frac{\phi(10^k)}{8}$.

$\lambda (n)$, compared to $\phi(n)$, makes it quite significantly easier to find the last $\ge 4$ digits of an exponentiated integer (depending on the exponent - the smaller lambda function may usually reduce the exponent more, but not necessarily).