# Thread: Proving a^b (mod n) ≡ [ a (mod n) ]^b

1. ## Proving a^b (mod n) = [ a (mod n) ]^b

How would one go about in order to prove

$\displaystyle a^b \mod{n} =\left [ a \mod{n} \right ]^b \, ?$

I would try doing something like this

$\displaystyle a \equiv b \mod{n} \ \Leftrightarrow \ \dfrac{a-b}{n} = k \, , \ \ k \in \mathbb{Z} \, ,$

however I'm not sure how to actually interpret $\displaystyle \left [ a \mod{n} \right ]^b$. It's periodic function which returns remainders and repeatedly so, what would it's algebraic expression perhaps be?

2. ## Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

Let $\displaystyle a=x+kn$

$\displaystyle 0\le x<n$

$\displaystyle x,k,n \in \mathbb{Z}$.

Then you have $\displaystyle (x+kn)^b (\mod n) \equiv ((x+kn) \mod n)^b (\mod n)$

Simplify that.

3. ## Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

How would one go about in order to prove

$\displaystyle a^b \mod{n} \equiv \left [ a \mod{n} \right ]^b \, ?$
Your notation is strange. Either you have a relation $\displaystyle x\equiv y\pmod{n}$ or you have a function x mod n, which returns the remainder when x is divided by n. In the first case, you can't use mod in both sides of the relation. In the second case, you can't use $\displaystyle \equiv$, or, at least, you need to define it.

4. ## Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

Originally Posted by emakarov
Your notation is strange. Either you have a relation $\displaystyle x\equiv y\pmod{n}$ or you have a function x mod n, which returns the remainder when x is divided by n. In the first case, you can't use mod in both sides of the relation. In the second case, you can't use $\displaystyle \equiv$, or, at least, you need to define it.
You are correct, let me fix that.

Originally Posted by a tutor
Let $\displaystyle a=x+kn$

$\displaystyle 0\le x<n$

$\displaystyle x,k,n \in \mathbb{Z}$.

Then you have $\displaystyle (x+kn)^b (\mod n) \equiv ((x+kn) \mod n)^b (\mod n)$

Simplify that.
Thanks!

5. ## Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

Originally Posted by a tutor
Let $\displaystyle a=x+kn$

$\displaystyle 0\le x<n$

$\displaystyle x,k,n \in \mathbb{Z}$.

Hmm
Then you have $\displaystyle (x+kn)^b (\mod n) \equiv ((x+kn) \mod n)^b (\mod n)$

Simplify that.
Hm, I would appreciate if you could show me the simplificaton, the multiple mods are confusing me.

6. ## Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

Following emakarov's comments perhaps it would be better if we used a % b for the remainder when a is divided by b.

Then rather than

$\displaystyle (x+kn)^b (\mod n) \equiv ((x+kn) \mod n)^b \ (\mod n)$

we have

$\displaystyle (x+kn)^b\ \%\ n \equiv ((x+kn)\% \ n)^b \ (\mod n)$

$\displaystyle (x+kn)^b\ \% \ n \equiv x^b \ (\mod n)$

One last step?

7. ## Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

if one uses [a] for the remainder of a, upon division by the integer n (where this remainder is between 0 and n-1, inclusive), we can state this as:

[ab] = [[a]b]. note that [a] is just an integer.

this can be shown using induction on b:

for b = 1:

[a] = [[a]], since 0 ≤ [a] ≤ n-1.

assume that for b = k,

[ak] = [[a]k].

then:

[ak+1] = [(a)(ak)] = [[a][ak]] (see below)

= [[a][[a]k]] (by our inductive hypothesis)

= [[[a]][[a]k]] (by our base case, [a] = [[a]])

= [[a][a]k] (again, see below)

= [[a]k+1]

(the crucial step is this:

[[x][y]] = [xy].

note that if x = tn + c, y = un + d, where 0 ≤ c,d < n that:

xy = (tn + c)(un + d) = (tun + c + d)n + cd. writing cd = wn + f, for 0 ≤ f < n, xy = (tun + c + d + w)n + f,

so we have:

[[x][y]] = [cd] = f = [xy]. one can view this as "a rule for brackets and multiplying": remove the outer 2 brackets on each side, and the innermost pair, multiply and add outer brackets).