1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ "* (mod n)" ? That's not multiplication. $\endgroup$ – Karolis Juodelė Apr 20 '14 at 18:18
5
+50
$\begingroup$

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 $< 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,\,$ so it follows by applyimg the Polynomial Rule with $\,f(x) = x^{\rm b}).$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.