<s>[INST] How do you calculate the modulo of a really high number with a large power, with a really high mod number? I need to work out $516489222^{22} \pmod{96899}$. I know there are easier ways of working this out, but am really struggling.
 [/INST] Note that $516489222 \equiv 17552 \pmod{96899}$. This gives
$$ 516489222^{22} \equiv 17552^{22} \pmod{96899}.$$
Now it is easy to calculate
\begin{align*}
17552^{2^{1}} &\equiv 30783 \pmod{96899}\\
17552^{2^{2}} &\equiv 30783^{2} \equiv 17768 \pmod{96899}\\
17552^{2^{3}} &\equiv 17768^{2} \equiv 4882 \pmod{96899}\\
17552^{2^{4}} &\equiv 4882 ^{2} \equiv 93669 \pmod{96899}.
\end{align*}
Since $22 = 2^{4} + 2^{2} + 2^{1},$ it follows that
\begin{align*}
17552^{22}
&\equiv 17552^{2^{4}} \cdot 17552^{2^{2}} \cdot 17552^{2^{1}} \pmod{96899} \\
&\equiv 93669 \cdot 17768 \cdot 30783 \pmod{96899} \\
&\equiv 4647 \pmod{96899}
\end{align*}
</s>