Exercise 3.1.22* (Primitive roots modulo $p$, if $p = 2q +1$, where $p,q$ are prime numbers.)

Question

Show that if $p$ and $q$ are primes, $p = 2q + 1$, and ${0<m <(p+1)^{1/2}}$, then $m$ is a primitive root $\pmod p$ if and only if it is a quadratic nonresidue $\pmod p$.

Richard Ganaye · Accepted Answer

\begin{proof} 
Let $p$ and $q$ be primes such that $p = 2q + 1$.

If $m$ is a primitive root modulo $p$, then $m$ is a quadratic nonresidue by Problem 21.

Conversely, suppose that $m$ is a quadratic nonresidue modulo $p$. I prove a stronger proposition : if $0 < m < p-1$, then $m$ is a primitive root (we must exclude $p-1$, since $p-1 \equiv -1 \pmod p$ has order $2$, so is not a primitive root). This is stronger, because $(p+1)^{1/2} \leq p-1$ ($\iff 0 \leq p(p-3)$).

Fix $g$ a primitive root modulo $p$. By Problem 11,  $m \equiv  g^t \pmod p$ for some odd integer $t$, where $0 < t < p-1$. Let $o(x)$ denote the order of an element $x$ modulo $p$, if $p 
mid x$. Then $o(g) = p-1$, and by Lemma 2.33,
$$o(m) = o(g^t) = \frac{o(g)}{t \wedge o(g)} = \frac{p-1}{t \wedge (p-1)} = \frac{2q}{t \wedge (2q)}.$$

Since $t$ is odd, $t \wedge (2q) = t \wedge q$, so we obtain
$$o(m) = \frac{2q}{t \wedge q}.$$
Assume for contradiction that $t \wedge q 
e 1$. Since $q$ is prime,  $q \mid t$, so $t = qs$ for some integer $s$. Since $0< t < p-1 = 2q$, we obtain $s = 1$, thus $t = q = (p-1)/2$. Then $m \equiv g^t \equiv g^{(p-1)/2} \pmod p$, thus $m^2 \equiv 1 \pmod p$, and $m
ot \equiv 1 \pmod p$, otherwise $g$ is not a primitive root, thus  $m \equiv -1 \pmod p$. This is impossible if $0 < m <p-1$. Therefore $t \wedge q = 1$, so that $o(m) = 2q = p-1$. Thus $m$ is a primitive root.

(Note that  if $p 
e 5$, $p \equiv 3 \pmod 4$, so that $-1$ is always a quadratic non residue modulo $p$, except $p = 5$.)

If $p = 2q +1$, where $p,q$ are prime numbers, every quadratic nonresidue $m$ modulo $p$, except $m \equiv -1 \pmod p$, is a primitive root modulo $p$.

\end{proof}

{\bf Verification with Sage.}
\begin{verbatim}
sage: q, p = 83, 167
sage: nr = [a for a in range(p) if kronecker(a,p) == -1]
sage: l = []
sage: for a in nr:
....:     l.append(Mod(a,p).multiplicative_order())
sage: print(l)
[166, 166, 166, 166, ..., 166, 166, 2]
\end{verbatim}

This shows that all nonresidues $m$ modulo $p = 167$, except $p-1$, are primitive roots.

Verification for all primes $p< 10000$ such that $q = (p-1)/2$ is prime :
\begin{verbatim}
sage: pr = prime_range(10000)
sage: prem = [p for p in pr if is_prime((p-1) // 2)]
sage: for p in prem:
....:     for a in range(2, p-1):
....:         if kronecker(a, p) == -1 and  Mod(a,p).multiplicative_order() != p-1:
....:             print(a,p)         
sage: 
\end{verbatim}
No counterexample to our proposition!

Exercise 3.1.22* (Primitive roots modulo $p$, if $p = 2q +1$, where $p,q$ are prime numbers.)

Answers

Comments

Exercise 3.1.22* (Primitive roots modulo $p$, if $p = 2q +1$, where $p,q$ are prime numbers.)

Answers

Comments

Add answer