prove for all $k \in \mathbb{Z_{\geq 0}}$ , $2^{2^{6k}\cdot4}\equiv 2^4\pmod{19}$ number theory prove for all $k \in \mathbb{Z_{\geq 0}}$ , $2^{2^{6k}\cdot4}\equiv 2^4\pmod{19}$
attempt:
$$2^{2^{6k}\cdot4}\equiv 2^4\pmod{19}$$
we can rewrite the equation
$$(2^4)^{2^{6k}}\equiv 2^4\pmod{19}$$
How I can continue from there to apply the Euler's theorem
 A: By Fermat's little theorem, we have
$$2^{18} \equiv 1 \pmod{19} \implies 2^{36} = (2^{4})^{9} \equiv 1 \pmod{19} \tag{1}\label{eq1A}$$
Since $2^6 = 64 \equiv 1 \pmod{9}$, we thus get $2^{6k} = (2^6)^k \equiv 1 \pmod{9}$, so there's an integer $j$ where $2^{6k} = 9j + 1$. Thus,
$$(2^4)^{2^{6k}} = (2^4)^{9j + 1} = ((2^4)^{9})^{j}(2^4) \equiv 2^4 \pmod{19} \tag{2}\label{eq2A}$$
A: You can reduce the exponent $\bmod \varphi(19)=18$, by Euler's theorem.
And now we can apply the Chinese Remainder Theorem:  $4\cdot2^{6k}\equiv4\bmod9$, since $\varphi(9)=6$  (Euler's theorem again),  and of course $4\cdot2^{6k}\equiv0\bmod2$.
So $4\cdot2^{6k}\equiv4\bmod{18}$.
A: Induction:
\begin{align*}2^{2^{6(k+1)}\cdot 4}=2^{2^{6k+6}\cdot 4}=\left(2^{2^{6k}\cdot 4}\right)^{64}&\equiv (2^4) ^{64}\mod 19\\&\equiv 2^{256}\mod19\end{align*}
By Fermat's little theorem, $2^{18}\equiv 1\mod 19$. Since $256=18*14+4$, then
\begin{align*}2^{2^{6(k+1)}\cdot 4}&\equiv (2^{18})^{14}2^4\mod19\\&\equiv 1^{14}2^4\mod 19\\&\equiv 2^4\mod19\end{align*}
A: well if $2^{6k}4\equiv m \pmod {18}$ then $2^{2^{6k}4}\equiv 2^m \pmod {19}$.
$2^{6k}4 \equiv 0 \pmod 2$ and $\phi(9) = 6$ so $2^6 \equiv 1 \pmod 9$ so $2^{6k}4\equiv 4 \pmod 9$.  So by Chinese remainder theorem there is one solution $\pmod {18}$ to $2^{6k}4\equiv 0 \pmod 2$ and $6^{6k}4\equiv 4 \pmod 9$.
And that unique solution is $4$
And that's that.
$2^{6k}4 \equiv 4 \pmod{18}$.  So there exists an $M$ so that $2^{6k}4=18M + 4$ so $2^{2^{6k}4}=2^{18M + 4} \equiv 2^4 \pmod{19}$.
