# Proof that $(a)^n \bmod n^2 = (a \bmod n)^n \bmod n^2$

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 you use $\equiv$, then you should congruence notation; but you aren't using congruence notation, you are using $\bmod$ as a binary operator, so you should not use $\equiv$, you should use $=$. – Arturo Magidin Feb 27 '12 at 6:07
don't quite understand how, all the mods in the above link are mod c, whereas here it would be different, for instance: (42 mod 31)^32 mod 31^2 does not equal (42)^32 mod 31^2 – user996522 Feb 27 '12 at 6:25
Oh, I see; missed that missing square. Sorry. – Arturo Magidin Feb 27 '12 at 6:27

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$.

-