Define
$$R_{p}=\{ r \mid r: \text{primitive root of p}, 1 \le r \le p \}$$
and also
$$Q_{p}=\{ a \mid a: \text{quadratic residue of p}, 1 \le a \le p \}$$
$$Q_p^c=\{a \mid a: \text{quadratic nonresidue of p}, 1 \le a \le p \}$$When $p$ is a prime number and $p=4k+3$ for some $k \in \Bbb{Z}$, find a formula for $(\sum_{r \in R_p}r)$. And also, find a formula for $(\sum_{a \in Q_p}a)$.
This looks so messy, so I'll explain this really interesting topic (at least very much for me).
When $p \equiv 1\pmod 4$, it is really easy to calculate the sum of all the elements in $R_p$, which I call 'the least positive primitive root residual system$\pmod p$'. I'm just a beginner for Number Theory so I don't know if there is a special name to the set… I just named it for convenience.
Anyway, when $p \equiv 1\pmod 4$, it is fairly easy to show that when $r$ is a primitive root of p, so does $(-r)$. It is also easy to show that there are $\phi(p-1)$ many primitive roots. So the result is
$$\left(\sum_{r \in R_p}r\right)=p \frac{\phi(p-1)}{2}$$
But when $p \equiv 3\pmod 4$, this logic doesn't apply anymore because when $r$ is a primitive root, then $(-r)$ is not a primitive root. The following is the list of primitive roots when $p=11, 19, 23$.
$$\begin{array}{rclcl} p=11; &r=2, 6, 7, 8 \end{array}$$
$$\begin{array}{rclcl} p=19; &r=2, 3, 10, 13, 14, 15 \end{array}$$
$$\begin{array}{rclcl} p=23; &r=5, 7, 10, 11, 14, 15, 17, 19, 20, 21 \end{array}$$
The frustrating thing is that when $p=11, 23$ the sums of the primitive roots are prime numbers($23$ and $139$ respectively). The interesting thing is that when $p=19$, the sum is $57$, which actually fits the rule above as if $p \equiv 1\pmod 4$. So I was wondering if there exists a formula for the sum of the least positive primitive roots when $p \not \equiv 1 \pmod 4$.
As for the sum of primitive roots, I couldn't find any rule for the formula. However, as for the sum of quadratic residues, the prospect is much brighter. First, when $p \equiv1 \pmod 4$, if $a$ is a quadratic residue of p, so does $(-a)$, which is quite similar to the primitive root case. Since we know that the number of quadratic residue is $\frac{p-1}{2}$, we get
$$\left(\sum_{a \in Q_p}a\right)=\left(\sum_{a \in Q_p^c}a\right)=\frac{p(p-1)}{4}$$
which is beautiful. Moreover, when $p=4k+3$, I did find a rule that (no, it was a wrong guess)
$$\begin{array}{rclcl} \left(\sum_{a \in Q_p}a\right)=kp, &\left(\sum_{a \in Q_p^c}a\right)=(k+1)p \end{array}$$
For example, when $p=11$, quadratic residues are $1, 3, 4, 5, 9$ so the sum is $22=2*11$. Quadratic nonresidues are $2, 6, 7, 8, 10$ and the sum is $33=3*11$.
But I failed to prove this. The hard thing here is that when $p \equiv3 \pmod 4$, if $a$ is a quadratic residue of p, then $(-a)$ is not a quadratic residue of p. I couldn't find any more useful Lemma to prove this. And I did find some stuff regarding about this, but most of them was way over my understanding of Elementary Number Theory.
Summary When $p \equiv3 \pmod 4$, is there a simple formula for the sum of the least positive primitive roots? Moreover, is it possible to prove the sum of the least positive quadratic residues which I can understand rather easily?
Thanks!
Edited Alas, my guess was wrong about the sum of the least quadratic residues. When $p=23$, the least positive quadratic residues are
$$1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18$$
and the sum is $92=4*23$. According to my previous guess, it should be $5*23=115$. So I was wrong… And I found a lot of useful information about the congruence, especially that the sum of primitive roots modulo p equals $\mu(p-1)$. And it is also easy to show that the sum of quadratic residues modulo p equals $0$. Maybe this is the limit of my ability. It is so hard to predict how big the sum would be relative to the number $p$ in either case.
Best Answer
When $p=3 \pmod 4$, there is still a simple formula for adding all of the primitive roots.
There probably is no easy answer here. The primitive roots of 7 are 3 and 5, adds to 8, and for 11, one has 2, 6, 7 and 8, which adds to 23.
One can establish that the primitive roots add up to a number modulo $p$, specifically $(-1)^m$, where $m$ is the number of distinct prime divisors of $p-1$, and if $p-1$ is divisible by a power of a prime, then the sum of primitive roots is a multiple of $p$.
The proof of this is fairly straight forward. Consider for example, $30$. The sum of the complete solutions of $x^n \pmod p$ is $0$, where $n \mid p-1$
So one works through the divisors. For $n=1$, the sum is 1. For $n=p_1$, q prime the sum is -1. For $n=p_1 p_2$, the sum is +1. The sum of all of the divisors of $p_1 p_2$, is then $f(1)+f(p_1)+f(p_2)+f(p_1 p_2) = 0$.
For powers of $p_n$, the sum $f(1)+f(p_1)+f(p^2_1) \dots$, is zero, so every term after the second must be zero.
Since the primitive roots is the largest divisor of $p-1$, then it is by that formula.