How can calculate $ a \mod n^2 $ be computed smartly if we know $a \mod n$? By example: > How can $ 2^{65536} \mod 7^2 $ be computed smartly? I think that there is a faster method than writing next element and find cycles. I found that $\mod 7 :$ $$ \color{red}{ 2^{0} \equiv 1\\\2^{1} \equiv 2\\\2^{2} \equiv 4}\\\2^{3} \equiv 1 $$ and by these equations each number can be fastly computed for example: $$2^{65536} = 2^{21845\cdot 3 +1 } \equiv 2^1 \equiv 2 $$ but how can it be applied for $\mod 49$?

$$ 2^3 = 1 + 7 \implies 2^{21} = (1+7)^7 \equiv 1 \bmod 7^2 \implies 2^{65536} \equiv 2^{65536 \bmod 21} = 2^{16} \equiv 23 \bmod 7^2. $$ The key point is the binomial expansion of $(1+7)^7$.