Results 1 to 5 of 5

Math Help - Primitive Root of odd prime p

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Primitive Root of odd prime p





    [also under discussion in math links forum]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Let  p\equiv 1 \mod{4} \text{ and } k\mid p-1 be even.
    Then  (-g)^k = g^k \not\equiv 1 \mod{p} since  g is a primitive root.

    If  k\mid p-1 is odd, then  (-g)^k = -g^k , but  g^k \not\equiv -1 \mod{p} for this would mean  g^{2k} \equiv 1 \mod{p} which we know to be false since  2k < p-1 .

    Therefore  -g is a primitive root if  p\equiv 1 \mod{4} .


    If  p\equiv 3 \mod{4} then  p=4k+3 , so  \frac{p-1}{2}=2k+1 i.e.  \frac{p-1}{2} is odd. Therefore  (-g)^{\frac{p-1}{2}} = -g^{\frac{p-1}{2}} .

    Now since  2\mid p-1, \; g^{p-1} = \left(g^{\frac{p-1}{2}}\right)^2 . Let  x=g^{\frac{p-1}{2}} .

    We know  x^2 \equiv 1 \mod{p} \implies p\mid (x+1)(x-1) \implies x\equiv 1 \text{ or } -1 \mod{p} . But since  g is a primitive root,  x \not\equiv 1 \mod{p} \implies x\equiv -1 \mod{p}.

    Therefore  (-g)^{\frac{p-1}{2}} = -g^{\frac{p-1}{2}} \equiv (-1)(-1) = 1 \mod{p} . Hence  -g is not a primitive root for  p\equiv 3 \mod{4} .
    Last edited by chiph588@; March 1st 2010 at 11:07 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by kingwinner View Post




    [also under discussion in math links forum]

    http://www.mathhelpforum.com/math-he...ive-roots.html

    Tonio
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    Quote Originally Posted by chiph588@ View Post
    Let  p\equiv 1 \mod{4} \text{ and } k\mid p-1 be even.
    Then  (-g)^k = g^k \not\equiv 1 \mod{p} since  g is a primitive root.

    If  k\mid p-1 is odd, then  (-g)^k = -g^k , but  g^k \not\equiv -1 \mod{p} for this would mean  g^{2k} \equiv 1 \mod{p} which we know to be false since  2k < p-1 .

    Therefore  -g is a primitive root if  p\equiv 1 \mod{4} .
    Hi, thanks for your help! I have some questions about your proof.

    1) When you say k|p-1 is odd or k|p-1 is even, do you include the case k=p-1? Or are you only referring to the divisors of p-1 that are strictly less than p-1?


    2) Also, how do you know that 2k is strictly less than p-1? (i.e. 2k < p-1?)


    Thank you very much!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    1.) Yes, I meant to say k is strictly less than p-1

    2.) What's the smallest divisor of p-1 not equal to 1? The answer is 2.

    Therefore  \frac{p-1}{2} is the largest divisor strictly less than p-1.

    But we know  \frac{p-1}{2} = 2n and  k\mid p-1 is odd.

    So, since  k \neq \frac{p-1}{2} and  \frac{p-1}{2} is the largest proper divisor we have  k<\frac{p-1}{2}

    i.e.  2k < p-1 .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: June 19th 2011, 01:56 PM
  2. Replies: 1
    Last Post: February 27th 2011, 06:59 PM
  3. sophie germain prime primitive root
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 24th 2010, 10:17 AM
  4. primitive root of a prime
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 13th 2009, 09:39 PM
  5. Primitive pth root of unity of a prime p
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 23rd 2008, 07:38 AM

Search Tags


/mathhelpforum @mathhelpforum