1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Congruent Integers

  1. Feb 18, 2010 #1
    1. The problem statement, all variables and given/known data
    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 ak is congruent to bk (mod n).

    2. Relevant 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...

    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.
  2. jcsd
  3. Feb 19, 2010 #2


    Staff: Mentor

    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
    am [itex] \equiv [/itex] bm mod n.

    Now use this assumption to show that the proposition is true for k = m + 1. I.e., that
    am + 1 [itex] \equiv [/itex] bm + 1 mod n.

    Something that might be helpful is that if p [itex] \equiv [/itex] q mod n, then p - q [itex] \equiv [/itex] 0 mod n.
  4. Feb 19, 2010 #3


    User Avatar
    Science Advisor

    Simpler, I think. [itex]a^k- b^k= (a- b)(a^{k-1}+ a^{k-2}b+ \cdot\cdot\cdot ab^{k-2}+ b^{k-1})[/itex]. Now use the fact that, since a= b (mod n), a- b is a multiple of n.
  5. Feb 19, 2010 #4


    Staff: Mentor

    That's similar to the direction I was sending the OP, but didn't want to get dinged again for giving too much help...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook