Proving Congruent Integers: Tips & Advice

[scottstapp]

Homework Statement

I need to prove the following but have no idea how to do so.

Let a,b, k be integers with k positive. If a is congruent to b(mod n), then a^k is congruent to b^k (mod n).

Homework Equations

The hint given is that I can assume the following proposition is true and that I am supposed to use it to show the statement holds for k=2,3...

Proposition:
If a is congruent to b(mod n) and c is congruent to d(mod n) then a+c is congruent to b+d(mod n)

Thanks for your help, I am pretty lost on this so anything helps.

 

[Mark44]

The directions of this problem seem to be pointing you to doing it by induction on k. For k = 1, the proposition is obviously true.

Assume the proposition is true for k = m. IOW, assume that
a^m $\equiv$ b^m mod n.

Now use this assumption to show that the proposition is true for k = m + 1. I.e., that
a^{m + 1} $\equiv$ b^{m + 1} mod n.

Something that might be helpful is that if p $\equiv$ q mod n, then p - q $\equiv$ 0 mod n.

 

[HallsofIvy]

Simpler, I think. $a^k- b^k= (a- b)(a^{k-1}+ a^{k-2}b+ \cdot\cdot\cdot ab^{k-2}+ b^{k-1})$. Now use the fact that, since a= b (mod n), a- b is a multiple of n.

 

[Mark44]

That's similar to the direction I was sending the OP, but didn't want to get dinged again for giving too much help...