Proof that $ (a)^n \bmod n^2 = (a \bmod n)^n \bmod n^2$
I did try a couple of examples and they do seem to work, but I just can't get why it works.
Proof that $ (a)^n \bmod n^2 = (a \bmod n)^n \bmod n^2$
I did try a couple of examples and they do seem to work, but I just can't get why it works.
If $n=1$, then the result is trivially true since both sides are $0$.
If $n\gt 1$, then write $a= r + kn + qn^2$, with $0\leq r \lt n$, $0\leq k\lt n$, so $a\bmod n = r$ and $a\bmod n^2 = r+kn$. Your question is whether $a^n\equiv r^n\pmod{n^2}.$ Using the binomial theorem, we have: $\begin{align*} a^n &\equiv (r+kn)^n \pmod{n^2}\\ &\equiv r^n + \binom{n}{1}r^{n-1}kn + \binom{n}{2}r^{n-2}(kn)^2 + \cdots + (kn)^n\pmod{n^2}\\ &\equiv r^n + r^{n-1}kn^2\pmod{n^2}\\ &\equiv r^n\pmod{n^2}, \end{align*}$ so the congruence always holds. Hence your equality always holds.
Here is another argument:
For any $k$, we compute using the binomial theorem that $(a + k n)^n = a^n + n a^{n-1} k n + \dfrac{n(n-1)}{2} a^{n-2} k^2 n^2 + \cdots,$ where all the terms after the first are divisible by $n^2$.
Thus we see that the congruence class of $a^n$ mod $n^2$ depends only on the congruence class of $a$ mod $n$.