Results 1 to 6 of 6

Math Help - modulo orders

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    11

    modulo orders

    Hi, I am not sure about my answer.

    Given a is an integer with (a,66)=1, what are the possible orders for a modulo 66?

    Working:
    Since phi(66)=20 then the possible orders of a modulo 66 have to divide this. So the possible orders are 1,2,4,5,10,20.

    Is this adequate?

    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: modulo orders

    Quote Originally Posted by alexgeek101 View Post
    Is this adequate?
    Yes.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2011
    Posts
    11

    Re: modulo orders

    Thanks alex.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,369
    Thanks
    739

    Re: modulo orders

    actually, no. some orders might not be possible, even from that list. for example, 20 is only possible if U(66) is cyclic, that is, has a generator.

    for example, <5> = {1,5,25,59,31,23,49,47,37,53}, that is 5 has order 10 (mod 66).

    since we have (5^k)^10 = 5^(10k) = (5^10)^k =1^k = 1 (mod 66), none of these numbers can have order 20.

    (this does however, guarantee elements of orders of 2,5 and 10 exist).

    also, <7> = {1,7,49,13,25,43,37,61,31,19} so 7 is of order 10, and none of THESE numbers have order 20.

    now, any cyclic group of order 20 has φ(20) = 8 generators, but we've eliminated 15 out of the 20 elements of U(66)

    as possibilities, so that leaves only 5 left and 5 < 8.

    so order 20 is not a possibility (even though it looked like it could be).

    is order 4 possible? since 4 does not divide 10, we have to look among the numbers we haven't tried so far:

    17, 29, 35, 41, and 65.

    now 17^2 = 25, 17^4 = (25)^2 = (5^2)^4 = 5^8 = 37. so 17 is not of order 2 or 4, so has to be of order 5 or 10.

    17^5 = 35, so 17 is of order 10. one may check that <17> = {1,17,25,37,35,49,41,31,65},

    so there are no elements of order 4, either.

    so in actual point of fact, the only possible orders are: 1,2,5, and 10.
    Last edited by Deveno; October 6th 2011 at 09:04 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: modulo orders

    Quote Originally Posted by Deveno View Post
    since 4 does not divide 20...
    Uh oh!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,369
    Thanks
    739

    Re: modulo orders

    in my defense, i point out that the "1" key and the "2" key on my keyboard are mere millimeters away.....i fixed it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  2. orders of groups
    Posted in the Advanced Algebra Forum
    Replies: 12
    Last Post: April 19th 2009, 10:58 AM
  3. help with a proof on orders
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 2nd 2009, 09:14 PM
  4. Partial orders
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: January 19th 2009, 10:58 AM
  5. Orders of iinfinity
    Posted in the Calculus Forum
    Replies: 5
    Last Post: June 6th 2008, 11:55 AM

Search Tags


/mathhelpforum @mathhelpforum