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: Order of an Integer mod m (number theory help!)

  1. Oct 23, 2006 #1
    Ok, my question is:

    Show that if ab == 1 mod m, then

    (Note that == means congruent) and ord(m)a means the order of a mod m

    I know that if a^k==1 mod m, then the ord(m)a is the smallest integer k such that the congruence holds. For example,
    ord(10)7=4 since 7^4==1 mod m.

    I'm thinking, a^(ord(m)a)==1 mod m so maybe ab=a^ord(m)a and also:
    b^(ord(m)b)==1 mod m so ab=b^ord(m)a

    Am i on the right track? Thanks!
  2. jcsd
  3. Oct 24, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I dislike unnecessary notation, so suppose the order of a is m, then what is 1^m=(ab)^m? Similarly if the order of b is n, what is 1^n=(ab)^n? Thus...? (remember the order is characterized by minimilality.)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook