Proving $\, a^b = (a\bmod n)^b\, \pmod{\!n}\ $ [Congruence Power Rule] I am working on a problem I am pretty close to solving but I can't figure out the last part. I used some algebraic manipluation to break the problem down. The problem is:


  Show that the following congruence is true
  
  a^b = ((a mod n)^b) (mod n)
  
  for any positive integers a, b, and n.
  
  Hint: Number a can be written as a = q*n + r, where q = floor brackets a/n, and r = a mod n.


My attempt it:


  (q*n +r)^b = ((a mod n)^b) * (mod n)
  
  (q*n)^b + (a mod n)^b = ((a mod n) ^b) * (mod n)
  
  (a)^b -(r)^b = ((a mod n) ^b) * (mod n)
  
  (a)^b = modn  ----> divided by ((a mod n)^b)


Am I doing this correctly and if so how can I prove this is true? Is there a trick I am missing? I think that by simplifying it further I would just keep going in a loop.

Thanks!
Let $\ A = (a\ {\rm mod}\ n).\,$  Then $\ A \equiv a \,\Rightarrow\,  A^b \equiv a^b\pmod n\,$ by the Congruence Power Rule below.



Congruence Sum Rule $\rm\qquad\quad  A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#c0f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#c0f}{A+B - (a+b)} $

Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \  B\equiv b\ \Rightarrow\ \color{blue}{AB\equiv ab}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{blue}{AB - ab} $

Congruence Power Rule $\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \  (mod\ m)$

Proof $\ $ It is true for $\rm\,n=1\,$ and $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ by the Product Rule, so the result follows by induction on $\,n.$

Polynomial Congruence Rule $\ $ If $\,f(x)\,$ is polynomial with integer coefficients then  $\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.$

Proof $\ $ By induction on $\, n = $ degree $f.\,$ Clear if $\, n = 0.\,$ Else $\,f(x) = f(0) + x\,g(x)\,$ for $\,g(x)\,$ a polynomial with integer coefficients of degree $&lt; n.\,$  By induction $\,g(A)\equiv g(a)\,$ so $\, \color{#0a0}{A g(A)\equiv a g(a)}\,$ by the Product Rule. Hence $\,f(A) = f(0)+\color{#0a0}{Ag(A)}\equiv f(0)+\color{#0a0}{ag(a)} = f(a)\,$ by the Sum Rule. 

Beware $ $ that such rules need not hold true for other operations, e.g.
the exponential analog of above $\rm A^B\equiv\, a^b$ is not generally true (unless $\rm B = b,\,$ when it follows by applying the Polynomial Rule with $\,f(x) = x^{\rm b}).$
We have
$$a = c \pmod{n}$$ This means $n \mid (a-c)$, i.e., $a-c = nd$. Now consider $a^b-c^b$. We have
$$a^b-c^b = (a-c) \left(a^{b-1} + a^{b-2}c + a^{b-3}c^2 + \cdots + ac^{b-2} + c^{b-1} \right) = nd\left(a^{b-1} + a^{b-2}c + a^{b-3}c^2 + \cdots + ac^{b-2} + c^{b-1} \right)$$
Hence, $$n \mid \left(a^b-c^b \right) \implies a^b \equiv c^b \pmod{n}$$