How would one go about in order to prove

I would try doing something like this

however I'm not sure how to actually interpret . It's periodic function which returns remainders and repeatedly so, what would it's algebraic expression perhaps be?

Printable View

- Aug 6th 2012, 02:47 AMMathCrusaderProving a^b (mod n) = [ a (mod n) ]^b
How would one go about in order to prove

I would try doing something like this

however I'm not sure how to actually interpret . It's periodic function which returns remainders and repeatedly so, what would it's algebraic expression perhaps be? - Aug 6th 2012, 04:57 AMa tutorRe: Proving a^b (mod n) ≡ [ a (mod n) ]^b
Let

.

Then you have

Simplify that. - Aug 6th 2012, 05:09 AMemakarovRe: Proving a^b (mod n) ≡ [ a (mod n) ]^b
Your notation is strange. Either you have a relation 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 , or, at least, you need to define it.

- Aug 6th 2012, 07:34 AMMathCrusaderRe: Proving a^b (mod n) ≡ [ a (mod n) ]^b
- Aug 6th 2012, 07:40 AMMathCrusaderRe: Proving a^b (mod n) ≡ [ a (mod n) ]^b
- Aug 6th 2012, 08:43 AMa tutorRe: 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

we have

One last step? - Aug 6th 2012, 12:35 PMDevenoRe: 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:

[a^{b}] = [[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,

[a^{k}] = [[a]^{k}].

then:

[a^{k+1}] = [(a)(a^{k})] = [[a][a^{k}]] (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).