# Sums of Primitive Roots and Quadratic Residues when $p \equiv 3\pmod 4$

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.

• – lab bhattacharjee Nov 10 '13 at 7:25
• – lab bhattacharjee Nov 10 '13 at 7:30
• @labbhattacharjee Thanks for the links. But the product of primitive roots is much much easier than the summation. And it was interesting to know about the congruence of the summation(still on a way to understand the proof) but what I'm really interested is the sum itself of the least positive primitive roots, not just the congruent relationship. – Taxxi Nov 10 '13 at 7:55
• @TaxxiDriver also related : math.stackexchange.com/questions/533338/… – Ewan Delanoy Nov 10 '13 at 9:56
• For the sum of quadratic residues (in the case $p\equiv3\pmod4$) Noam Elkies gave an answer here. The sum is related to the class number of the imaginary quadratic number field $\Bbb{Q}(\sqrt{-p})$. – Jyrki Lahtonen Nov 10 '13 at 10:04

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.

• Well, I already know that the sum of primitive roots is congruent to $\mu(p-1)$, and what you have explained seems to be a concise version of the proof. By the way, it would be really glad if you could fill in the $x^{n} \pmod p$ thing. Since there is no $\equiv$ sign there, I got stuck understading your explanation. Thanks anyway! – Taxxi Nov 10 '13 at 9:15