I recently had an exam in my number theory class and one of the questions was to compute the last seven digits of $7^{5^{2024}}$. Usually, this is a pretty standard problem since we can just use FLT and CRT (see below for my approach). However, that we need to compute the last seven digits makes this method seem completely intractable for an exam since we will need to compute many large powers and then find solutions $ax + by = 1$ for very large numbers in order to run CRT. This makes me think there must be another way to think about this computation. Perhaps another way is to work $p$-adically. Namely, I thought about the map $x \mapsto x^5$ on elements of $\mathbb{Z}_2$ and $\mathbb{Z}_5$ to try to solve for $7^{5^{2024}}$ mod $2^7$ and mod $5^7$. However, I am still encountering large computations. Does anyone have any ideas? There is probably something simple that I have missed.
Here is if we only wanted the last three digits: This is the same as computing $7^{5^{2024}} \pmod{1000}$. Since $\varphi(1000) = 400$, by FLT, $7^{400} = 1$, so computing $5^{2024} \pmod {400}$ helps simplify things. Sadly, $(5,400) \neq 1$, but we can still use CRT. Clearly $5^{2024} \equiv 0 \pmod {25}$. See that $5^4 \equiv 1 \pmod{16}$. Via division alg/bezout's find $9\cdot25-16\cdot14 = 1$, i.e. $225$ is 1 mod 16 and 0 mod 25, so $5^{2024} \equiv 225 \pmod {400}$, so then $7^{5^{2024}} \equiv 7^{225} \pmod{1000}$. From here, probably can just use CRT again and compute powers $7^{2^i}$ to make computations as painless as possible. But even in the three-digit case, the computation already seems to be involved.
Thanks very much!
Best Answer
Notice $\ 7^{\Large 5^{\large\color{#c00}{N+4}}}\!\!\equiv 7^{\Large 5^{\large \color{#c00}{N}}}\!\!\pmod{\!10^{\large 7}}\ $ for $\ \color{#c00}N\ge\color{#c00} 5,\,$ so the rest is easy.
Proof: $\, \ 7^{\Large 5^{\large\color{#c00}{N+4}}}\!\!\!- 7^{\Large 5^{\large \color{#c00}{N}}}\!\! = 7^{\Large 5^{\large \color{#c00}{N}}}\! (7^{\Large\color{#0a0}{ 5^{\large \color{#c00}N} (5^{\Large 4}-1)}}-1)\equiv 0\,$ by mod order $\rm\color{#0a0}{reduction}$ via below $\qquad\ \ \ \ \begin{align} 7^{\large 4}\equiv 1\!\!\!\!\pmod{\!5^{\large 2}}&\overset{(\ \ )^{\large 5^5\!}} \Longrightarrow 7^{\Large \color{#0a0}{4\cdot 5^{\Large\color{#c00}5}}}\!\!\!\equiv 1\!\!\!\!\pmod{\!5^{\large 7}},\ {\rm and}\,\ \color{#0a0}{4\cdot 5^{\large\color{#c00}{5}}\mid 5^{\color{#c00}N}(5^{\large 4}\!-\!1)}\\ 7^{\large 2}\equiv 1\!\!\!\!\pmod{\!2^{\large 4}}&\overset{(\ \ )^{\large 2^3\!}}\Longrightarrow 7^{\Large \color{#0a0}{2^4}}\!\equiv\ 1\!\!\!\pmod{\!2^{\large 7}}\,\ \ {\rm and}\quad\ \ \ \color{#0a0}{2^{\large 4}\mid 5^{\color{c00}N}(5^{\large 4}\!-\!1)}\end{align}\qquad\qquad$
by repeatedly applying $\mu$LTE to Lift The Exponents (by powering the congruence).