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

Printable View

- Apr 23rd 2010, 07:00 PMsantiagos11sophie 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). - Apr 24th 2010, 04:04 AMtonio

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

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

Tonio - Apr 24th 2010, 08:34 AMsantiagos11
shouldn't this be $\displaystyle \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? - Apr 24th 2010, 08:57 AMtonio
- Apr 24th 2010, 09:17 AMsantiagos11
ok thanks, you know sometimes we see the hard things easily and the easy things are hard to see!