1. Not finding help here? Sign up for a free 30min 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!

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

    shmoe

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Congruence Question
Loading...