Results 1 to 4 of 4

Math Help - Primitive roots

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    1

    Primitive roots

    [FONT='Times New Roman','serif']Let r be a primitive root of the odd prime p . Prove the following.[/FONT]
    [FONT='Times New Roman','serif']If p is congruent to 3(mod 4), then -r has order (p-1)/2 modulo p.[/FONT]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Etrain27 View Post
    [FONT='Times New Roman','serif']Let r be a primitive root of the odd prime p . Prove the following.[/FONT]
    [FONT='Times New Roman','serif']If p is congruent to 3(mod 4), then -r has order (p-1)/2 modulo p.[/FONT]
    r^{p-1} \equiv 1(\bmod p) \implies (r^{(p-1)/2} -1)(r^{(p-1)/2}+1)\equiv 0(\bmod p).
    Thus, r^{(p-1)/2}\equiv 1,-1(\bmod p) it cannot be 1 because the order of r is p-1.
    Thus, r^{(p-1)/2}\equiv -1(\bmod p).
    This tells us, \left( -r \right)^{(p-1)/2} = (-1)^{(p-1)/2}r^{(p-1)/2}\equiv (-1)(-1) = 1(\bmod p) because p\equiv 3(\bmod 4).

    Now we need to prove that if 1\leq k\leq p-1 is order of -r then k=(p-1)/2.
    By the above result we see that k|(p-1)/2, since (p-1)/2 is odd it follows that k must be odd.
    But then, (-r)^k = -r^k\equiv 1(\bmod p)\implies r^k \equiv -1(\bmod p).
    Also, r^{(p-1)/2} \equiv -1(\bmod p)\implies r^{(p-1)/2} \equiv r^k (\bmod p).
    Using properties of primitive roots and orders it means (p-1)/2 \equiv k(\bmod p-1)\implies k=(p-1)/2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2008
    Posts
    2
    Looking at your reply to the question in this thread, I have a question very similiar to the one posted originally and am sure that you would be able to help me out also quite simply.

    Let r be a primitive root of the odd prime p. If p=1(mod 4), then -r is also a primitive root of p.

    I would appreciate the help on this question, I am sure there will be a similar question on my final next week.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by theotheleo View Post
    Let r be a primitive root of the odd prime p. If p=1(mod 4), then -r is also a primitive root of p.
    Let k be the order of -r.
    We claim that k cannot be odd. Suppose that k is odd.
    Then (-r)^k = -r^k \equiv 1(\bmod p) \implies r^k \equiv -1(\bmod p).
    Again r^{(p-1)/2}\equiv -1(\bmod p) which will force k=(p-1)/2.
    But that is a contradiction because p\equiv 1(\bmod 4) so (p-1)/2 is even.
    Since k is even it mean (-r)^k = r^k and so the order must be the same as r, i.e. p-1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 10th 2011, 06:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 17th 2008, 09:09 PM
  3. Primitive roots
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 15th 2007, 10:19 AM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 21st 2006, 08:05 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2006, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum