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