1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – user236182 Oct 28 '15 at 19:50
  • $\begingroup$ i thought because p was odd that p(p-1) = odd times even = even... $\endgroup$ – Kees Til Oct 28 '15 at 19:53
  • 1
    $\begingroup$ But if $p(p-1)$ is even, then not necessarily $\frac{p(p-1)}{2}$ is even. $\endgroup$ – user236182 Oct 28 '15 at 19:53
  • $\begingroup$ o i see it know thats quite stupid xD, any other ideas for this problem? $\endgroup$ – Kees Til Oct 28 '15 at 19:55
  • 1
    $\begingroup$ 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$. $\endgroup$ – lulu Oct 28 '15 at 19:56
1
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.