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!

Solution 1:

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.\ $ More generally we have

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

See here for further congruence rules and properties.

Solution 2:

Hint: Let $a^b = (qn+r)^b$. Expand the right-hand side using the binomial theorem and see what you can discard as being $\equiv 0 \bmod n$.

Solution 3:

Given that $ x = y \mod n $ is not a multiplication, but just a statement that $ x-y = an $ for some integer $a$, and that $$ (x+y)^b \neq x^b + y^b $$ (as you seem to imply in the step leading from (q*n +r)^b to (q*n)^b + (a mod n)^b...)

Whay you can do is simply express your power as a binomial power, like: $$ a^b = (qn+r)^b = (qn)^b + b·(qn)^{b-1}r + \binom{b}{2}(qn)^{b-2}r^2 + \dots + b·qn·r^{b-1} + r^b $$ (the $\binom{n}{k}$ number is the binomial number, anyway it's not relevant at all)

Now, all the monomials on the right are divisible by $n$ except for the last one $r^b$. So you have $$a^b=r^b\mod n$$