Results 1 to 4 of 4

Math Help - Order

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Order

    Let \text{GCD}(r,s)=1, r,s>2, and suppose [a^d]_r is the order of a mod r, and [a^e]_s is the order of a mod s. Let m=rs. Show that [a^{\text{LCM}[d,e]}]_m is the order of a mod m.

    So we know:
    r|(a^d-1)\iff a^d\equiv 1 \ (\text{mod r})
    s|(a^e-1)\iff a^e\equiv 1 \ (\text{mod s})

    Now, what?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    Re: Order

    Your notation is terribly confusing. You're saying that d is the order of a mod r, and e is the order of a mod s, and thus that lcm(e,d) is the order of a mod rs?

    Hint: use the Chinese remainder theorem. There is an isomorphism (\mathbb{Z}/rs\mathbb{Z})^* \simeq (\mathbb{Z}/r\mathbb{Z})^* \times (\mathbb{Z}/s\mathbb{Z})^*.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Re: Order

    Quote Originally Posted by Bruno J. View Post
    Your notation is terribly confusing. You're saying that d is the order of a mod r, and e is the order of a mod s, and thus that lcm(e,d) is the order of a mod rs?

    Hint: use the Chinese remainder theorem. There is an isomorphism (\mathbb{Z}/rs\mathbb{Z})^* \simeq (\mathbb{Z}/r\mathbb{Z})^* \times (\mathbb{Z}/s\mathbb{Z})^*.
    I am not sure what do by using the CRT but here is what we have:

    a^d\equiv 1 \ (\text{mod r})
    a^e\equiv 1 \ (\text{mod s})

    So a^d+rt=a^e+sb=1

    a^d+rt\equiv a^e \ (\text{mod s})

    I don't know how I am supposed to proceed.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    Re: Order

    Do you know a bit of algebra? What is the order of an element in the direct product of two finite groups?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Re-writing higher order spatial derivatives as lower order system
    Posted in the Differential Equations Forum
    Replies: 11
    Last Post: July 27th 2010, 08:56 AM
  2. Replies: 1
    Last Post: October 27th 2009, 04:03 AM
  3. Replies: 2
    Last Post: February 23rd 2009, 05:54 AM
  4. Replies: 2
    Last Post: November 25th 2008, 09:29 PM
  5. Replies: 4
    Last Post: August 12th 2008, 04:46 AM

Search Tags


/mathhelpforum @mathhelpforum