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.
 A: The useful property is $$(x\mod{n})(y\mod{n})\equiv(xy \mod{n})$$ If you iterate this, it works for integer powers too.  That means that the OP is equal to $$(616489222 \mod{96899})^{22}\pmod{96899}\equiv 17552^{22}\pmod{96899}$$
We can use the property again, noting that $(x^2)^{11}\pmod{n}\equiv (x^2\mod{n})^{11}\pmod{n}$.  Hence $$17522^{22}\pmod{96899}\equiv (17522^2\mod{96899})^{11}\pmod{96899}\equiv44452^{11}\pmod{96899}$$
A few more steps like this and you'll be done.  This process can be made quicker by using Wolfram Alpha, which can handle unwieldy arithmetic, including the OP in one step.
A: 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*}
