# Let $p$ and $q = 2p + 1$ be odd primes. Show that $(−1) ^{\frac{p−1}{ 2}} 2$ is a primitive root modulo q.

Let $p$ and $q = 2p + 1$ be odd primes. Show that $(−1) ^{\frac{p−1}{ 2}} 2$ is a primitive root modulo q.

We see that our number must have order $q-1$ to be a primitive root. If we check the divisors which are $1,2,p,2p$ and see that $\left((−1) ^{\frac{p−1}{ 2}} 2\right)^\frac{q-1}{d} \equiv 1 \pmod{q}$ we are finished.

Obviously $1$ and $2$ fail so we need to check $p$.

$p = \frac{q-1}{2}$, so we see $\left((−1) ^{\frac{p−1}{ 2}} 2\right)^\frac{q-1}{d} \equiv \left((−1) ^{\frac{p−1}{ 2}} 2\right)^2 \equiv 4 \pmod{q}$. So this fails as well. The only one to check is $2p$ but that is equal to $q-1$ so we are finished.

Kees

• It's not given that $p\equiv 1\pmod{4}$, so not necessarily $\left((−1) ^{\frac{p−1}{ 2}} 2\right) ^ p \equiv 2^p \pmod{q}$. It's true if $p\equiv 1\pmod{4}$, but if $p\equiv 3\pmod{4}$, then we get $-2^p$. – user236182 Oct 28 '15 at 19:50
• i thought because p was odd that p(p-1) = odd times even = even... – Kees Til Oct 28 '15 at 19:53
• But if $p(p-1)$ is even, then not necessarily $\frac{p(p-1)}{2}$ is even. – user236182 Oct 28 '15 at 19:53
• o i see it know thats quite stupid xD, any other ideas for this problem? – Kees Til Oct 28 '15 at 19:55
• Well, the only possible orders an element can have mod($q$) are divisors of $q-1$, hence $1,2,p, 2p$. Easy to rule out $1,2$. Just need to show that your number can't have order $p$. – lulu Oct 28 '15 at 19:56

I.e. we want to prove $\left((-1)^{\frac{p-1}{2}}2\right)^{d}\not\equiv 1\pmod{q}$ for all $d\in\{1,2,p\}$.
If $(-1)^{\frac{p-1}{2}}2\equiv 1\pmod{q}$, then $\pm 2\equiv 1\pmod{q}$, so $q=3$, which is not of the form $2p+1$.
If $\left((-1)^{\frac{p-1}{2}}2\right)^2\equiv 1\pmod{q}$, then $4\equiv 1\pmod{q}$, i.e. $q=3$, which is not of the form $2p+1$.
If $\left((-1)^{\frac{p-1}{2}}2\right)^p\equiv 1\pmod{q}$, then we check two cases:
$1)\ \$ $p\equiv 1\pmod{4}$. Then $\left((-1)^{\frac{p-1}{2}}2\right)^p\equiv 2^p\pmod{q}$, so $2^p\equiv 1\pmod{q}$. By Euler's criterion $2^p\equiv 2^{\frac{q-1}{2}}\equiv \left(\frac{2}{q}\right)\pmod{q}$, so we must have $\left(\frac{2}{q}\right)=1$, i.e. by Quadratic Reciprocity $q\equiv \pm 1\pmod{8}$. However, also $q=2p+1\equiv 2\cdot 1+1\equiv 3\pmod{4}$, so $q\equiv -1\pmod{8}$, so $-1\equiv 2p+1\pmod{8}$, i.e. $p\equiv 3\pmod{4}$, which contradicts $p\equiv 1\pmod{4}$.
$2)\ \$ $p\equiv 3\pmod{4}$. Then $\left((-1)^{\frac{p-1}{2}}2\right)^p\equiv -2^p\pmod{q}$, so $-2^p\equiv 1\pmod{q}$. By Euler's criterion $2^p\equiv 2^{\frac{q-1}{2}}\equiv \left(\frac{2}{q}\right)\pmod{q}$, so we must have $\left(\frac{2}{q}\right)=-1$, i.e. by Quadratic Reciprocity $q\equiv \pm 3\pmod{8}$. However, also $q=2p+1\equiv 2\cdot 3+1\equiv 3\pmod{4}$, so $q\equiv 3\pmod{8}$, so $3\equiv 2p+1\pmod{8}$, i.e. $p\equiv 1\pmod{4}$, which contradicts $p\equiv 3\pmod{4}$.