Results 1 to 5 of 5

Math Help - Prove: If ab congruent to 1 (mod m), then o(a) equals o(b).

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    12

    Prove: If ab congruent to 1 (mod m), then o(a) equals o(b).

    So far, all I can figure out is that a and b are units (mod m). Also, a is the inverse of b, and b is the inverse of a. Say o(a) = c and o(b) = d. I want to show that c = d. I am unsure on how to do this.

    I also know:
    a^c is congruent to 1 (mod m)
    b^d is congruent to 1 (mod m)
    ab is congruent to 1 (mod m)

    ...and I'm lost from here on.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Geoffrey View Post
    So far, all I can figure out is that a and b are units (mod m). Also, a is the inverse of b, and b is the inverse of a. Say o(a) = c and o(b) = d. I want to show that c = d. I am unsure on how to do this.

    I also know:
    a^c is congruent to 1 (mod m)
    b^d is congruent to 1 (mod m)
    ab is congruent to 1 (mod m)

    ...and I'm lost from here on.
    What does it mean o(a) and o(b)?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2006
    Posts
    12
    o(a) means the order of some integer a in (mod m). In other words, the order is the least positive integer power k such that a^k is congruent to 1 (mod m).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Let us say that,
    ab\equiv 1

    And that a^k\equiv 1 is smallest positive integer (its order).

    Then, (ab)^k=a^kb^k=b^k \equiv 1
    Thus, b^k=1.
    Let us assume there is a smaller j<k such as,
    b^j\equiv 1
    Then,
    (ab)^j= a^jb^j\equiv a^j\equiv 1
    Which contradicts the assumption that k was the smallest.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2006
    Posts
    12
    I see, so that makes sense. If o(a) is not equal to o(b), there is a contradiction. Thank you so much for your time!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: March 14th 2011, 08:06 AM
  2. Prove recurrence relation equals sum of permutations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 16th 2010, 10:00 AM
  3. Replies: 1
    Last Post: October 6th 2009, 12:11 AM
  4. Replies: 2
    Last Post: February 5th 2009, 03:27 PM
  5. prove a congruent angle with a bisector
    Posted in the Geometry Forum
    Replies: 2
    Last Post: June 18th 2007, 03:12 PM

Search Tags


/mathhelpforum @mathhelpforum