Results 1 to 4 of 4

Thread: 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 $\displaystyle t $ always divides $\displaystyle \phi(m) $.

    Here, $\displaystyle \phi(45)=24 $ and $\displaystyle 11 \not| 24 $ so no number exists with order $\displaystyle 11 $ modulo $\displaystyle 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 $\displaystyle a\in G \leq \mathbb{Z}/m\mathbb{Z} $, then the order of $\displaystyle a $ divides $\displaystyle |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 $\displaystyle a\in \mathbb{Z}/m\mathbb{Z} $ is a primitive root, then we know that $\displaystyle \mathbb{Z}/m\mathbb{Z} = <a> $ i.e. $\displaystyle \forall \; b\in \mathbb{Z}/m\mathbb{Z}, \; b=a^k $ for some $\displaystyle k\in \mathbb{N} $.


    So all one has to do to find $\displaystyle ord_m(b) $ for any $\displaystyle b\in \mathbb{Z}/m\mathbb{Z} $, is find $\displaystyle ord_m(a) $ and use the formula $\displaystyle 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: Oct 1st 2011, 09:05 AM
  2. [SOLVED] order of elements in multiplicative group
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Apr 28th 2009, 10:04 AM
  3. multiplicative
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 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: Jan 29th 2008, 02:36 PM

Search Tags


/mathhelpforum @mathhelpforum