Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruence Question

  1. Sep 30, 2006 #1
    Congruence Question !!

    I have a question regarding congruences, I could not find this result in the textbooks.

    (note to readers: a^k means a to the power k, and = means congruent)

    If we have a congruence: a^m = a^n (mod p) for a,m,n,p>0

    It seems likely to deduce that m = n (mod p)

    However after attempting a homework question, I discover that

    a^m = a^n (mod p) implies m = n (mod p-1)

    Is this result true? How does one go about to formally prove the above statement?

    Thank you...
  2. jcsd
  3. Sep 30, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    What made you think that's true? Did you try some numerical examples?
  4. Oct 1, 2006 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    One would first go about thinking what the correct statement of the above should be: one raised to any power is still one.
  5. Oct 1, 2006 #4
    Consider a^m = a^n (mod p) => m = n (mod p) for m=p, n=1. Then it's obviously not true, and proof that it's not true follows immediately from the little fermat theorem.

    Hint: the little fermat theorem is key to understanding the 2nd set of congruences as well
    Last edited: Oct 1, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook