I'm having trouble understanding clever applications of Fermat's Little Theorem and its generalization, Euler's Theorem. I already understand the derivation of both, but I can't think of ways to use them in problems that I know I must use them (i.e. the question topic is set).
Here are two questions I had trouble with trying to use FLT and ET:
-
Find the 5th digit from the rightmost end of the number $N = 5^{\displaystyle 5^{\displaystyle 5^{\displaystyle 5^{\displaystyle 5}}}}$.
-
Define the sequence of positive integers $a_n$ recursively by $a_1=7$ and $a_n=7^{a_{n-1}}$ for all $n\geq 2$. Determine the last two digits of $a_{2007}$.
I managed to solve the second one with bashing and discovering a cycle in powers of 7 mod 1000, and that may be the easier path for this particular question rather than using ET. However, applying ET to stacked exponents I believe is nevertheless an essential concept for solving more complex questions like number 1 that I wish to learn. It would be helpful if I could get hints on using ET in those two problems and a general ET approach to stacked exponents and its motivation.
Best Answer
For the first problem you will need a little bit of Chinese Remainder Theorem. You want to find the remainder of the stacked exponential modulo $10^5 = 2^5 \times 5^5$. Consider the two prime divisors separately.
As $\phi(2^5) = 16$ we have that if $r_1$ is the remainder of $5^{5^{5^{5}}}$ modulo $\phi(2^5) = 16$ then $5^{5^{5^{5^{5}}}} \equiv 5^{r_1} \pmod {2^5}$. Now we have to find $r_1$, which is a solution of $5^{5^{5^{5}}} \equiv r_1 \pmod {2^4}$. Repeat this algorithm few times and you will get rid of the exponents and you will find a value such that: $5^{5^{5^{5^{5}}}} \equiv r \pmod {2^5}$. Now use that $5^{5^{5^{5^{5}}}} \equiv 0 \pmod {5^5}$ and glue the two solutions with Chinese Remainder Theorem.
The second one can be solved using similar method, but this time you won't need the Chinese Remainder Theorem, as $(7,100) = 1$. Actually this is easier as $7^4 \equiv 1 \pmod {100}$.