<s>[INST] Square of a mod 
Find $9^{16} \pmod{25}$ by separation.

The separation means, that $25 = 5^2$. 
But $9^{16} \equiv 1 \pmod{5}$, so I how I derive that $9^{16} \equiv 16 \pmod{25}$?
 [/INST] As $9=3^2,9^{16}=(3^2)^{16}=3^{32}$
Now $3^3\equiv2\pmod{25}\implies3^{32}=3^2(3^3)^{10}\equiv3^2\cdot2^{10}$
Now $2^5\equiv7\implies2^{10}=(2^5)^2\equiv7^2\equiv-1$
$\implies3^2\cdot2^{10}\equiv9\cdot-1\equiv16$
</s>