Results 1 to 4 of 4

Math Help - Multiplicative Order

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    8

    Multiplicative Order

    Hi all, just wondering what the method is to find an integer with order t mod m.

    For example, find all integers that have order 11 (mod 45).

    I know you can geuss and test, but I'm thinking there must be a faster way.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by seven.j View Post
    Hi all, just wondering what the method is to find an integer with order t mod m.

    For example, find all integers that have order 11 (mod 45).

    I know you can geuss and test, but I'm thinking there must be a faster way.

    Thanks.
    Well for starters, the order  t always divides  \phi(m) .

    Here,  \phi(45)=24 and  11 \not| 24 so no number exists with order  11 modulo  45 .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by seven.j View Post
    Hi all, just wondering what the method is to find an integer with order t mod m.

    For example, find all integers that have order 11 (mod 45).

    I know you can geuss and test, but I'm thinking there must be a faster way.

    Thanks.
    Also, if  a\in G \leq \mathbb{Z}/m\mathbb{Z} , then the order of  a divides  |G| .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    One last thing:

    If  a\in \mathbb{Z}/m\mathbb{Z} is a primitive root, then we know that  \mathbb{Z}/m\mathbb{Z} = <a> i.e.  \forall \; b\in \mathbb{Z}/m\mathbb{Z}, \; b=a^k for some  k\in \mathbb{N} .


    So all one has to do to find  ord_m(b) for any  b\in \mathbb{Z}/m\mathbb{Z} , is find  ord_m(a) and use the formula  ord_m(b) = ord_m(a^k)=\frac{ord_m(a)}{(ord_m(a),k)} .

    In summary, knowing the order of a primitive root gives you the order of every number in your group.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Multiplicative order
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: October 1st 2011, 09:05 AM
  2. [SOLVED] order of elements in multiplicative group
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 28th 2009, 10:04 AM
  3. multiplicative
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 18th 2008, 06:22 PM
  4. is phi multiplicative
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 14th 2008, 07:22 AM
  5. Multiplicative Set
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 29th 2008, 02:36 PM

Search Tags


/mathhelpforum @mathhelpforum