5
$\begingroup$

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?

$\endgroup$
6
  • $\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$ Commented Apr 16, 2015 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$ Commented Apr 16, 2015 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$ Commented Apr 16, 2015 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$ Commented Apr 16, 2015 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$ Commented Apr 26, 2015 at 20:45

1 Answer 1

Reset to default
-1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.