<s>[INST] How do I solve $18^{{20}^{19}}$ divided by 7? I was re-practicing some number theory and I came across this question that I had previously solved and it seems like... I can't solve it anymore. My thoughts are that $18^6 \equiv 1 \text{ mod } 7$ by Euler's formula so I am looking to express the power $20^{19}$ as some $6k + r$ to simplify the system. Doing this I get:
$$20 \equiv 2  \text{ mod } 6\\ 20^2 \equiv 4\text{ mod } 6\\ 20^3 \equiv 2 \text{ mod } 6$$
...and there seems to be no end as they repeat in 2, 4, 2 cycles. I can't seem to simplify this equation any other way though.. Could someone please enlighten me and suggest ways of viewing (or improving) on my problem solving skills when attacking problems like these?
 [/INST] Since $\gcd(18,7)=1$, by Euler's theorem, $18^{\phi(7)}\bmod{7}=1$.
Since $7$ is prime, $\phi(7)=7-1=6$.
Therefore $18^{6}\bmod{7}=1$.

There exists a positive integer $n$ such that:
$20^{19}=$
$6n+(20^{19}\bmod{6})=$
$6n+((20\bmod{6})^{19}\bmod{6})=$
$6n+(2^{19}\bmod{6})$

Therefore:
$18^{20^{19}}\bmod{7}=$
$18^{6n+(2^{19}\bmod{6})}\bmod{7}=$
$18^{6n}\cdot18^{(2^{19}\bmod{6})}\bmod{7}=$
$(18^{6})^{n}\cdot18^{(2^{19}\bmod{6})}\bmod{7}=$
$(\color\red{18^{6}\bmod{7}})^{n}\cdot18^{(2^{19}\bmod{6})}\bmod{7}=$
$\color\red{1}^{n}\cdot18^{(2^{19}\bmod{6})}\bmod{7}=$
$18^{(2^{19}\bmod{6})}\bmod{7}$

Let's prove by induction that if $n$ is odd then $2^{n}\bmod{6}=2$:
First, show that this is true for $n=1$:
$2^{1}\bmod{6}=2$
Second, assume that this is true for $n=2k+1$:
$2^{2k+1}\bmod{6}=2$
Third, prove that this is true for $n=2k+3$:
$2^{2k+3}\bmod{6}=$
$2^{2k+2+1}\bmod{6}=$
$2^{2+2k+1}\bmod{6}=$
$2^2(2^{2k+1})\bmod{22}=$
$2^2(\color\red{2^{2k+1}\bmod{6}})\bmod{6}=$
$2^2(\color\red{2})\bmod{6}=$
$8\bmod{6}=$
$2$
Therefore, since $19$ is odd, $2^{19}\bmod{6}=2$.

From all of the above, we can conclude:
$\begin{align}
18^{20^{19}}\bmod{7}
 &= 18^{(20^{19}\bmod{6})}\bmod{7} \\
 &= 18^{(2^{19}\bmod{6})}\bmod{7} \\
 &= 18^{2}\bmod{7} \\
 &= 324\bmod{7} \\
 &= 2 
\end{align}
$
</s>