Once again 2016 simplified

[Note: The naive euler's theorem approach does not appear to yield a simple answer to this problem.]

Define $S_{m}=\{n \in N: \forall a, b\in N^{+} n^{a} \equiv n^{b} (\text {mod }10^{m})\}$ . This means that if a number is in $S_{m}$ then the rightmost $m$ digits will not change when we raise this number to any positive integer power.

Claim: If $A \in S_m$ and $A \equiv 6 \pmod{10}$ , then $A^ 5 \in S_{m+1}$ .

Proof: Let $A = 10^m B + C$ where $0 \leq C < 10^m$ .
We are given that $A^2 \equiv A \pmod{ 10^m } \Rightarrow C^2 \equiv C \pmod{10^m} \Rightarrow 10^m \mid C^2 - C$ .

To show that $A^5 \in S_{m+1}$ , we just need to show that $A^{10} \equiv A^5 \pmod{10^{m+1} }$ . Let's simplify this further.
Using the Binomial theorem, $A^{10} = (10^mB+C)^{10} \equiv C^{10} \pmod{10^{m+1} }$ .
Likewise, $A^5 = (10^mB+C)^5 \equiv { 5 \choose 1 } \times 10^m B \times C + C^5 \pmod{10^{m+1} }$ . Since $C$ is even, hence the first term is a multiple of $10 ^ { m + 1}$ , and so $A^5 \equiv C^5 \pmod{ 10 ^ {m+1} }$ .

As such, it is equivalent to show that $C^{10} \equiv C^5 \pmod{ 10 ^ { m + 1 } }$ , or that $10^{m+1} \mid C^{10} - C^5$ . Observe that:

$C^{10} - C^5 = C^5 (C^5 - 1) = C^5 \times (C-1) \times (C^4 + C^3 + C^2 + C + 1) = C^4 \times (C^2 - C) \times (C^4 + C^3 + C^2 + C + 1) .$

Now, since $C \equiv 6 \pmod{10}$ , thus $C ^4$ contributes a multiple of 2, and $C^4 + C^3 + C^2 + C + 1 \equiv 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod{5}$ so it contributes a multiple of 5. From above, we know that $C^2 - C$ is a multiple of $10^m$ . Hence we conclude that their product is a multiple of $10^{m+1}$ and we are done! $_ \square$

By induction, since $2016 \in S_1$ , thus $B = 2016^ { 5^{2014} } \in S_{2015}$ . Now, observe that the expression is equal to

$2016^{2015^{2014^{..^{2^{1}}}}} =(2016^{5^{2014^{..^{2^{1}}}}})^{( 403^{2014^{2013^{..^{2^{1}}}}})}$

As such, we just need to find the 2015th digit of $B$ . At this point, we can either use a big number calculator (which works for this greatly simplified value) or continue doing it by hand via concatenating power calculations.

---

Note: If $A \in S_m$ and $A \equiv 6 \pmod{10}$ and $A = 10^{m} B + C$ , then the $(m+1)$ -digit of $A^ 5$ is equal to 10 minus the $(m+1)$ digit of $C^2$ .

We can see that $\forall n >= 403 \quad \text{we have} \quad 2016^n \equiv 2016^{n + 5^{2014}} \mod 10^{2015}$

Then $\large 2016^{2015^{2014^{2013^{..^{..^{3^{2^{1}}}}}}}} \equiv 2016^{5^{2014}} \mod 10^{2015}$

Big calculator the result is 2