This may be a very basic number theory question, but I don't understand:
Why does $a^b \bmod c = (a \bmod c)^b \bmod c$
This may be a very basic number theory question, but I don't understand:
Why does $a^b \bmod c = (a \bmod c)^b \bmod c$
Suppose that x \;\mathrm{mod}\; n = x' \;\mathrm{mod}\; n and y \;\mathrm{mod}\; n = y' \;\mathrm{mod}\; n.
Then it must be the case that x=x'+nk and y=y'+n\ell for some $k,\ell \in \mathbb{Z}$.
Thus xy=(x' +nk)(y'+n\ell) = x'y' + n(y'k+x'\ell+nk\ell). In other words, $xy$ and x'y' differ by a multiple of $n$. Therefore, xy \;\mathrm{mod}\; n = x'y' \;\mathrm{mod}\; n.
This says multiplication (mod $n$) does not depend on the exact choice of integers just the remainders.
Now to apply to your situation. $a \;\mathrm{mod}\; n = (a \;\mathrm{mod}\; n)\;\mathrm{mod}\;n$ so $a^2 \;\mathrm{mod}\; n = a\cdot a \;\mathrm{mod}\; n = (a \;\mathrm{mod}\; n) \cdot (a \;\mathrm{mod}\; n) \;\mathrm{mod}\;n =(a \;\mathrm{mod}\; n)^2 \;\mathrm{mod}\;n$.
To get higher powers just repeat (use induction).
Edit: I should also mention, the same thing is true of addition mod $n$. Adding does not depend on the exact integers, just their remainders. You can prove this much the same way I did for multiplication:
x \;\mathrm{mod}\; n = x' \;\mathrm{mod}\; n and y \;\mathrm{mod}\; n = y' \;\mathrm{mod}\; n then x+y \;\mathrm{mod}\; n = x'+y' \;\mathrm{mod}\; n.
As Leslie mentions in the comments above, it is must easier (better) to deal with modular arithmetic in terms of congruence classes. What I did above says that we can multiply congruence classes by multiplying any two representatives of those classes (the same for addition). In "abstract algebra" language, we are discovering that equivalence classes mod $n$ have a ring structure (in fact, we are just looking at the quotient ring $\mathbb{Z}/n\mathbb{Z}$).
By the definition of congruence, you want to show that $c$ divides $(\mbox{some number congruent to a})^b - a^b$. This means you want to show that $c$ divides $(a + ck)^b - a^b$ for some $k$. Expand the expression and you should be able to show this is true.
Hint $\rm\ \ c\ |\ (a + n\:c)^b - a^b\:$ is the special case $\rm\ R = \mathbb Z,\ \ f(x) = x^b,\ \ x = a+n\:c\ $ in the
Factor Theorem $\rm\ \ \ \ \ \ x-a\ \ \,|\,\ \ f(x)\,-\,f(a)\ \ in\ \ R[x],\ $ for $\rm\ a\in R,\ \ f(x)\in R[x]$
or, said operationally: $\rm\ x\equiv a \Rightarrow f(x)\equiv\: f(a),\:$ a prototypical ring congruence inference.
See also my many posts on the Congruence Product Rule.
Because the canonical map from ${\bf Z}$ to ${\bf Z}/c{\bf Z}$ is a ring homomorphism.
If you are comfortable with $x\equiv y\bmod n\Rightarrow xz\equiv yz \;(\bmod n)$, then
$a\equiv (a \bmod c)\; (\bmod c)$
$a^b\equiv (a\bmod c)^b\; (\bmod c)$
$a^b \,\bmod c=(a\bmod c)^b\bmod c$.