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

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

    Mark44

    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

    HallsofIvy

    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

    Mark44

    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