If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$.

Question

If $p$ and $q = 2p + 1$ are both odd primes, show that $-4$ and $2(-1)^{(1/2)(p-1)}$ are both primitive roots modulo $q$.

I cannot get heads nor tails of how to even start this let alone finish it

Answer 1

Recall that $q$ has $\varphi(\varphi(q))$ primitive roots, that is, $p-1$ primitive roots. Also, there are $p$ quadratic non-residues modulo $q$. Since every primitive root is a NR, all but one quadratic non-residue of $q$ is a primitive root of $q$. Which one?

The prime $q$ is of the form $4k+3$, and therefore $-1$ is a quadratic non-residue of $q$. It is clear that $-1$ is not a primitive root. So to prove that $a$ is a primitive root of $q$, it is enough to show that $a$ is a NR of $q$ not congruent to $-1$.

(i) The case $a=-4$: Since $-1$ is a NR, and $4$ is clearly a QR, it follows that $-4$ is an NR. Since $-4$ is not congruent to $-1$ modulo $q$ ($q$ cannot be $3$), it is a primitive root of $q$.

(ii) The case $a=(-1)^{(p-1)/2}(2)$: Here you will be using the fact that $2$ is a NR of a prime $q$ if and only if $q$ is congruent to $\pm 3$ modulo $8$. There are two cases to consider, $q$ of the form $8k+3$ and $q$ of the form $8k+7$.

Remark: We describe a more group-theoretic approach. The primitive roots of $q$ are the objects $a$ of full order $q-1=2p$. The order of any $a$ divides $2p$, so to show $a$ is a primitive root it is enough to show that $a$ does not have order $2$ or $p$. The only element of order $2$ is $-1$. If $a$ has order $p$, one can show that $x^2\equiv a\pmod{q}$ has a solution, that is, $a$ is a quadratic residue of $q$. So to show $a$ is a primitive root it is enough to show that $a$ is a quadratic non-residue not congruent to $-1$.

Answer 2

Theorem: if $p$ is prime, $p\nmid a$ and for all prime divisors $q$ of $p-1$ we have $a^{(p-1)/q}\not\equiv 1\pmod{p}$, then $a$ is a primitive root mod $p$.

I'll prove three parts: If $p,q$ are odd primes and $q=2p+1$, then:

i) $-4$ is a primitive root mod $q$.

ii) if $p\equiv 1\pmod{4}$, then $2$ is a primitive root mod $q$.

iii) if $p\equiv 3\pmod{4}$, then $-2$ is a primitive root mod $q$.

i) We're left with proving $(-4)^2\not\equiv 1\pmod{q}$ and $(-4)^p\not\equiv 1\pmod{q}$.

The first one is clear, because $q>5$.

The second one is equivalent to $2^{2p}\not\equiv -1\pmod{q}$, i.e. $2^{q-1}\not\equiv -1\pmod{q}$, which is true by Fermat's Little theorem (and remember $q>5$).

ii) We want to prove that if $p\equiv 1\pmod{4}$, then $2^2\not\equiv 1\pmod{q}$ and $2^p\not\equiv 1\pmod{q}$.

The first one is clear, because $q>5$.

The second one is equivalent to $2^{(q-1)/2}\not\equiv 1\pmod{q}$. By Euler's Criterion this is equivalent to $\left(\frac{2}{q}\right)\not\equiv 1\pmod{q}$.

By Quadratic Reciprocity, this is true, because $q=2p+1=2(4k+1)+1=8k+3$.

iii) We want to prove that if $p\equiv 3\pmod{4}$, then $(-2)^2\not\equiv 1\pmod{q}$ and $(-2)^p\not\equiv 1\pmod{q}$.

The first one is clear, because $q>5$.

The second one is equivalent to $2^p\not\equiv -1\pmod{q}$, because $p$ is odd. This is equivalent to $2^{(q-1)/2}\not\equiv -1\pmod{q}$. By Euler's Criterion, this is equivalent to $\left(\frac{2}{q}\right)\not\equiv -1\pmod{q}$, which is true by Quadratic Reciprocity, because $q=2p+1=2(4k+3)+1=8k+7$.