6s - Problem 6

The solution to the problem is $x$ where $6^{6^{6^{6^{6^{6}}}}}\equiv x \mod 10^{6}$ . We see that $\gcd(6^{6^{6^{6^{6^{6}}}}},10^{6})\neq1$ . Thus, we reduce this modulo by dividing each term by $2^{6}$ as proven on a separate note. With that, we obtain $\frac{6^{6^{6^{6^{6^{6}}}}}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ . To solve this, we shall apply Euler's totient function repeatedly such that $\phi (5^{n})=5^{n-1}.2^{2}$ and $\phi (5^{n}.2^{k})=5^{n-1}.2^{k+1}$ . Hence: $\frac{6^{6^{6^{6^{6^{6}}}}}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ $\frac{6^{6^{6^{6^{6^{6}}}}(\mod5^{5}.2^{2})}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ $\textbf{**}$ Now, observe the index of $6$ , which is $6^{6^{6^{6^{6}}}}\equiv y\mod 5^{5}.2^{2}$ . As proven on a separate note, we can divide the terms by $2^{2}$ to obtain $\frac{6^{6^{6^{6^{6}}}}}{2^{2}}\equiv \frac{y}{2^{2}}\mod 5^{5}$ . Then, we apply the property of modulo arithmetic such that if $a\equiv b\mod n$ , then $ka\equiv kb\mod n$ for any integer $k$ . With that, we know that $\frac{6^{6^{6^{6^{6}}}}}{2^{2}}\equiv \frac{y}{2^{2}}\mod 5^{5}\Rightarrow6^{6^{6^{6^{6}}}}\equiv y\mod 5^{5}$ . Take note that we do not use this technique on $\frac{6^{6^{6^{6^{6^{6}}}}}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ so that we do not eliminate the $2^{6}$ . Doing so would result in finding congruence for $5^{6}$ and not $10^{6}$ . Hence we have: $\frac{6^{6^{6^{6^{6^{6}}}}(\mod5^{5}.2^{2})}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}\Rightarrow \frac{6^{6^{6^{6^{6^{6}}}}(\mod5^{5})}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ Repeating this steps above (indicated with $\textbf{**}$ )over and over again, we eventually get: $\frac{6^{6^{6^{6^{6^{6(\mod5)}(\mod5^{2})}(\mod5^{3})}(\mod5^{4})}(\mod5^{5})}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ Then, we shall solve this step by step: $\frac{6^{6^{6^{6^{6^{1}(\mod5^{2})}(\mod5^{3})}(\mod5^{4})}(\mod5^{5})}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ $\frac{6^{6^{6^{6^{6}(\mod5^{3})}(\mod5^{4})}(\mod5^{5})}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ $\frac{6^{6^{6^{31}(\mod5^{4})}(\mod5^{5})}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ $\frac{6^{6^{531}(\mod5^{5})}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}$ $\frac{6^{1156}}{2^{6}}\equiv \frac{x}{2^{6}}\mod5^{6}\Rightarrow2^{1150}.3^{1156}\equiv \frac{x}{2^{6}}\mod5^{6}$ Since $2^{1150}\equiv 5374\mod 5^{6}$ and $3^{1156}\equiv 15396\mod 5^{6}$ , we know that $2^{1150}.3^{1156}\equiv 3729\mod5^{6}$ . Therefore, $\frac{x}{2^{6}}=3729$ .

Finally, we compute our desired answer, $x$ to be $x=3729\times2^{6}=238656$ . The $6$ th digit from the right of $6^{6^{6^{6^{6^{6}}}}}$ is $\boxed{2}$ .

$\textbf{Proofs and workings used in solution}$

$1$ . If $m\equiv n\mod k$ with $\gcd(m,n,k)=b$ , then $\frac{m}{b}\equiv\frac{n}{b}\mod\frac{k}{b}$ . This property is valid because by mathematical reasoning, if $(m-n)$ divisible by $k$ , then obviously $\frac{m-n}{b}$ is divisible by $\frac{k}{b}$ . Alternatively, we may also proof this by observing that since $\frac{m-n}{k}=z$ where $z$ is an integer, then obviously $\frac{m-n}{k}=\frac{\frac{m-n}{b}}{\frac{k}{b}}=z$ , and this completes the proof.

$2$ . Finding remainder when $6^{4}$ divided by $5^{3}$ . $6^{4}\equiv 46\mod5^{3}$ $6^{2}\equiv36\mod5^{3}$ So, $6^{6}=46\times36=1656\equiv31\mod5^{3}$ .

$3$ . Similarly, finding remainder when $6^{31}$ divide $5^{4}$ . $6^{4}\equiv46\mod5^{4}$ $6^{3}\equiv216\mod5{4}$ Hence, $6^{31}=(6^{4})^{7}\times6^{3}\equiv46^{7}\times216 \mod5^{4}$ . Then, $46^{2}\equiv241\mod5^{4}$ and hence, $6^{31}\equiv241^{3}\times46\times216\mod5^{4}$ . $241^{2}\equiv581\mod5^{4}$ $6^{31}\equiv581\times241\times46\times216 \mod5^{4}\Rightarrow581\times241\times46\times216\equiv531\mod5^{4}$ $\therefore 6^{31}\equiv531 \mod 5^{4}$ Using these same steps as above, we can find $6^{531} \mod5^{5}$ , $2^{1150}\mod5^{6}$ and $3^{1156}\mod5^{6}$ .

can we apply log

To get the sixth digit on the right of the tetration ${}^6 6$ , we need all of the last six digits. We can extract them using $\begin{aligned} r_6&\equiv {}^6 6\mod 10^6 \end{aligned}$ Instead of doing that directly, it will be more helpful to prove the following solution to a (slightly) more general problem: $\begin{aligned} r_k&\equiv {}^k{6}\mod 2^i\cdot 5^k&&&\Leftrightarrow &&&& \begin{aligned} r_k&\equiv 0\mod 2^i\\ r_k&\equiv 6^{r_{k-1}}\mod 5^k \end{aligned}&&&&r_{k-1}&\equiv {}^{k-1} 6 \mod 2^2\cdot 5^{k-1},&&&i,\:k&\in\mathbb{N},& 2&\leq i\leq k&&&&&(1) \end{aligned}$ We notice: The congruence we have to solve for $r_{k-1}$ is of the same form as before, but the tetration is smaller!

Proof: We want to reduce the enormous exponential ${}^k6$ with Euler's Theorem . Sadly, $\gcd(6,\:2^i\cdot 5^k)=2$ , so we cannot use it directly! Instead we work with the Chinese Remainder Theorem, as $\gcd(2^i,\:5^k)=1$ : $\begin{aligned} r_k&\equiv {}^k 6\mod 2^i\cdot 5^k&&&\Leftrightarrow&&&&\begin{aligned} r_k&\equiv {}^k 6\mod 2^i\\ r_k&\equiv {}^k 6\mod 5^k \end{aligned}&&&&&&\left|\: {}^{k-1} 6\geq k\geq i\right.&&\Rightarrow&&\gcd({}^k 6,\:2^i\cdot 5^k)&=\gcd(6^{{}^{k-1} 6},\:2^i\cdot 5^k)=2^i \end{aligned}$ The first congruence is simply zero: We already know $2^i$ is a factor of ${}^k 6$ . The second congurence is harder, but now we can use Euler's Theorem as $\gcd(6,\:5^k)=1$ . The idea is to write the exponent ${}^{k-1} 6$ in terms of $\phi(5^k)=2^{2}\cdot 5^{k-1}$ : $\begin{aligned} {}^{k-1} 6&\overset{!}{=}c\phi(5^k)+r_{k-1}, &c&\in\mathbb{Z} &&&\Rightarrow&&&& r_k&\equiv {}^k 6\equiv 6^{{}^{k-1} 6}\equiv 6^{c\phi(5^k)}\cdot 6^{r_{k-1}}\equiv 1^{c}\cdot 6^{r_{k-1}}\equiv 6^{r_{k-1}}\mod 5^k&&&\blacksquare \end{aligned}$

To solve the original problem, we factor $10^6=2^6\cdot 5^6$ and use (1) repeatedly to get down to ${}^1 6=6$ : $\begin{aligned} \begin{aligned} r_6&\equiv 0\mod 2^6\\ r_6&\equiv 6^{r_5}\mod 5^6 \end{aligned}&&&&&&\begin{aligned} r_k&\equiv 0\mod 2^2\\ r_k&\equiv 6^{r_{k-1}}\mod 5^k \end{aligned}&&k&\in\{2;\:\ldots;\:5\}&&&&&r_1&\equiv 6\mod 20 \end{aligned}$ Though it is tedious, we can solve these six systems of congruences by hand using the power method (see reply), starting with $r_1$ and ending with $r_6$ . The results are listed below, the sixth digit on the right of $r_6$ is the answer: $\begin{array}{r|rrrrrr} k & 1 & 2 & 3 & 4 & 5 & 6\\\hline r_k & 6 & 56 & 156 & 1156 & 1156 & \boxed{2}38656 \end{array}$