Results 1 to 5 of 5

Thread: Primitive Root of odd prime p

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    405

    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 $\displaystyle p\equiv 1 \mod{4} \text{ and } k\mid p-1 $ be even.
    Then $\displaystyle (-g)^k = g^k \not\equiv 1 \mod{p} $ since $\displaystyle g $ is a primitive root.

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

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


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

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

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

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

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    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
    405

    Smile

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

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

    Therefore $\displaystyle -g $ is a primitive root if $\displaystyle 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 $\displaystyle \frac{p-1}{2} $ is the largest divisor strictly less than p-1.

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

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

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

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Jun 19th 2011, 12:56 PM
  2. Replies: 1
    Last Post: Feb 27th 2011, 05:59 PM
  3. sophie germain prime primitive root
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 24th 2010, 09:17 AM
  4. primitive root of a prime
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 13th 2009, 08:39 PM
  5. Primitive pth root of unity of a prime p
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Apr 23rd 2008, 06:38 AM

Search Tags


/mathhelpforum @mathhelpforum