sophie germain prime primitive root

**santiagos11** · April 23rd 2010, 07:00 PM

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).

**tonio** · April 24th 2010, 04:04 AM

Originally Posted by santiagos11

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

**santiagos11** · April 24th 2010, 08:34 AM

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?

**tonio** · April 24th 2010, 08:57 AM

Originally Posted by santiagos11

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

**santiagos11** · April 24th 2010, 09:17 AM

ok thanks, you know sometimes we see the hard things easily and the easy things are hard to see!

Thread: sophie germain prime primitive root

LinkBack

Thread Tools

Display

sophie germain prime primitive root

Similar Math Help Forum Discussions

Prove that if n>=2 and not prime, then n has a prime divisor p<=(sq.root)n

Prove if a is a primitive root mod p^2, then it is a primitive root mod p

Primitive Root of odd prime p

primitive root of a prime

Primitive pth root of unity of a prime p

Search Tags