Results 1 to 5 of 5

Math Help - sophie germain prime primitive root

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    37

    sophie germain prime primitive root

    Here p denotes a prime.
    Suppose q is a prime such that q=4n+1 where n is an interger.
    proof that 2 is a primitive root of p if p is of the form 2q+1.
    (sophie germain prime).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by santiagos11 View Post
    Here p denotes a prime.
    Suppose q is a prime such that q=4n+1 where n is an interger.
    proof that 2 is a primitive root of p if p is of the form 2q+1.
    (sophie germain prime).

    First, \phi(p)=p-1=2q\Longrightarrow ord_q(2)\in\{1,2,q,2q\} . Now, 1 obviously cannot be, and 2^2=1\!\!\!\pmod p\Longrightarrow p\mid 3 , which is also impossible.

    Now using Jacobi symbol, we know that \left(\frac{2}{p}\right)=2^{\frac{p-1}{2}}=2^q\!\!\!\pmod p , but since p=3\!\!\!\pmod 8\neq \pm 1\!\!\!\pmod 8 , then \left(\frac{2}{p}\right)=-1\Longrightarrow 2^q=-1\!\!\!\pmod p\Longrightarrow ord_p(2)\neq q , and thus...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    37
    shouldn't this be \phi(p)=p-1=2q\Longrightarrow ord_p(2)\in\{1,2,q,2q\}. (order mod p instead of mod q)
    And why is this implication true?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by santiagos11 View Post
    shouldn't this be \phi(p)=p-1=2q\Longrightarrow ord_p(2)\in\{1,2,q,2q\}. (order mod p instead of mod q)

    Yes. That was a typo.

    And why is this implication true?
    Because \{1,2,q,2q\} are the only numbers dividing p-1=2q ...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    37
    ok thanks, you know sometimes we see the hard things easily and the easy things are hard to see!
    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. Primitive Root of odd prime p
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 2nd 2010, 12:10 PM
  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