Power tower last digits

Question

Can anyone solve the following problem of finding the 6th last digit from the right of the decimal representation of the following number:

$6^{6^{6^{6^{6^{6}}}}}$

Essentially it means reducing this modulo $10^6$ and supposedly Chinese Remainder Theorem should be used, but I have no idea how to solve this. Can anyone help?

Answer 1

We're interested in $6^x \mod 10^6$; this is determined by $6^i \mod 2^6$ and $6^i \mod 5^6$. Mod $2^6$ it's easy: $6^x$ is divisible by $2^6$ if $x \ge 6$. $6$ is coprime to $5^6$ with multiplicative order $3125 = 5^5$ mod $5^6$. In fact, the multiplicative order of $6$ mod $5^m$ seems to be $5^{m-1}$ (prove!). So $$\eqalign{6 &\equiv 1 \mod 5\cr 6^6 &\equiv 6^1 = 6 \mod 5^2\cr 6^{6^6} &\equiv 6^6 \equiv 31 \mod 5^3\cr 6^{6^{6^6}} &\equiv 6^{31} \equiv 531 \mod 5^4\cr 6^{6^{6^{6^6}}} &\equiv 6^{531}\equiv 1156 \mod 5^5\cr 6^{6^{6^{6^{6^6}}}} &\equiv 6^{1156} \equiv 4281 \mod 5^6\cr }$$ and using Chinese Remainder, $$6^{6^{6^{6^{6^6}}}} \equiv 238656 \mod 10^6$$