I was exploring the layout of primitive roots of primes over a reasonable range and this question concerns the number of primitive roots either side of $p/2$.

Many primes have an exact match between what I call lower and upper primitive roots, those below and above $p/2$. For the most part, these are the primes $p\equiv 1 \bmod 4$ - these have primitive roots that are symmetric, $x$ is a primitive root meaning that $-x$ is also a primitive root.

However my question really concerns the primes $p\equiv 3 \bmod 4$. For these primes, the primitive roots are antisymmetric: $x$ being a primitive root implies that $-x$ is not a primitive root. In these cases there is some scatter but there is also a definite trend to have more primitive roots in the upper category. I can understand that there are more natural squares in $(0,p/2)$ than in $(p/2,p)$ but the imbalance trend seems to be slightly larger than that value as shown here in a plot of the upper root count minus lower root count:

enter image description here

Does anyone have some insight into what drives this imbalance in primitive roots, favoring higher values over lower?

  • $\begingroup$ This is a very interesting observation for which I can offer no explanation. Can you demonstrate that if p is prime and p==1(mod 4) and r is a primitive root then -r is also a primitive root. I understand that for such p the modulo multiplication group (mod p) would be isomorphic to the cyclic group of order 4k for some positive k. $\endgroup$ – Geoffrey Critzer Apr 16 '15 at 20:01
  • $\begingroup$ @GeoffreyCritzer - sure; for $p\equiv 1 \bmod 4$, a primitive root $g$ has order $(p-1) \equiv 0 \bmod 4$. For even values of $a, (-g)^a = g^a$ and in particular $(-g)^{(p-1)/2}=g^{(p-1)/2} \equiv -1 \bmod p$. A similar argument gives the anti-symmetric case for $p\equiv 3 \bmod 4$ $\endgroup$ – Joffan Apr 16 '15 at 20:17
  • $\begingroup$ Thanks Joffan, I want to make sure I understand the proof. In the last congruence: g^(p-1)/2==-1(mod p). Is this true because in a prime modulus if x^2==1 then x==1 or x== -1. In particular let x=g^(p-1)/2. But g^(p-1)/2 is not congruent to 1 because the order of g is p-1. So g^(p-1)/2== -1. $\endgroup$ – Geoffrey Critzer Apr 16 '15 at 22:28
  • $\begingroup$ @GeoffreyCritzer Yes, correct. And therefore also $(-g)^{(p-1)/2} \equiv -1$ and we know that since $(-g)^k = \pm g^k (\not\equiv 1 $ for $k<(p-1) \:),$ the order of $(-g)$ must also be $(p-1)$. Another way to get to the same idea is that $g^k \equiv-1$ for some $k<(p-1)$, and it can only be at $k=(p-1)/2$ since we know that $g^{2k}\equiv -1^2\equiv 1$ $\endgroup$ – Joffan Apr 16 '15 at 22:39
  • 1
    $\begingroup$ OK, Also would you agree that if g is a primitive root of a prime p that is congruent to 3 mod4 then the order of -g is (p-1)/2 and therefor is not a primitive root. For the first 10 primes that are congruent to 3 mod 4: 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71 I have the upper root count minus the lower root count as: 1, 0, 2, 2, 2, 0, 0, 4, 8, 0, 6. Have you considered submitting this to Sloane's OEIS. It will might get some attention from someone who can answer your great question. Do you still have access to the code for your plot. $\endgroup$ – Geoffrey Critzer Apr 26 '15 at 20:45

Primitive roots cannot also be quadratic residues since $\mathbb{Z}/p$ has even order. It can be shown that the sum of quadratic residues minus the sum of the nonresidues is negative: https://en.wikipedia.org/wiki/Quadratic_residue#Dirichlet.27s_formulas


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.