Results 1 to 4 of 4

Math Help - Primitive root question

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Primitive root question

    According to my book, 2 is a primitive root of 11 because:

    phi(11) = 10. 2^2 = 4 mod 11. 2^5 = -1 mod 11. 2^10 = 1 mod 11
    That's the whole explanation.

    I used to same logic to find a primitive root of 17.

    phi(17) = 16. 2^2 = 4 mod 17. 2^4 = -1 mod 17. 2^8 = 1 mod 17. 2^16 = 1 mod 16.
    But 2 is NOT a primitive root of 17???

    Whats going on here?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Primitive root question

    the order of an element, has to divide the order (size) of the entire group of units.

    for 11, U(11) has 10 elements, so the possible orders of elements of U(11) (which are all the integers mod 11 save 0, because 11 is prime), are 1,2,5 and 10.

    only 1 will have order 1. 2^2 = 4 ≠ 1, so 2 doesn't have order 2. 2^5 = -1 (or 10, doesn't matter), so 2^5 does not have order 5. that just leaves 10, and 2^10 = 1, as expected

    (all these values are mod 11, of course).

    now U(17) has 16 elements. possible orders are 1,2,4,8 or 16.

    while it is true that 2^16 = 1, that does not mean 2 has order 16. why? because 2^8 = 1, and 8 < 16, so 2 has order 8.

    not every element of U(17) will have order 16. for example 2^4 = 16 (mod 17). as you can easily see, 16 only has order 2.

    the upshot of this, is that 2 does not generate the entire set of units via powers, the powers of 2 are:

    {2,4,8,16,15,13,9,1}, which is only half of U(17) = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: Primitive root question

    How do you find a primitive root of 17? Well, you have already found that 2 has order 8. So if you can find an element x such that x^2=2\pmod{17}, then x will have order 2*8=16 in U(17) and will therefore be a primitive root.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Primitive root question

    and looking at integers of the form 17k+2, we have:

    2, 19, 36...i think i see a winner....
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive Root Question
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 22nd 2013, 03:33 AM
  2. Primitive Root Question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2010, 05:46 PM
  3. Primitive Root Question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 11th 2010, 11:17 AM
  4. primitive root question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 17th 2009, 07:33 PM
  5. one more primitive root question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 11th 2009, 04:59 AM

Search Tags


/mathhelpforum @mathhelpforum