Paper detail

New observations on primitive roots modulo primes

We make many new observations on primitive roots modulo primes. For an odd prime $p$ and an integer $c$, we establish a theorem concerning $\sum_g(\frac{g+c}p)$, where $g$ runs over all the primitive roots modulo $p$ among $1,\ldots,p-1$, and $(\frac{\cdot}p)$ denotes the Legendre symbol. On the basis of our numerical computations, we formulate 35 conjectures involving primitive roots modulo primes. For example, we conjecture that for any prime $p$ there is a primitive root $g<p$ modulo $p$ with $g-1$ a square, and that for any prime $p>3$ there is a prime $q<p$ with the Bernoulli number $B_{q-1}$ a primitive root modulo $p$. We also make related observations on quadratic nonresidues modulo primes and primitive prime divisors of some combinatorial sequences. For example, based on heuristic arguments we conjecture that for any prime $p>3$ there exists a Fibonacci number $F_k<p/2$ which is a quadratic nonresidue modulo $p$; this implies that there is a deterministic polynomial time algorithm to find square roots of quadratic residues modulo a prime $p>3$.