We know that when $q$ is a prime $1(\text{mod } 4)$ then $$\sum_{R_i}R_i = q(q-1)/4,$$ where $R_i$ are all the quadratic residues $\text{mod } q$. I was curious if there is a similar (or some sort of) formula when $q$ is a prime $3(\text{mod } 4)$. Thanks!

Yes, there's a formula, though not quite as simple: the sum is $$\frac12 \left( {q \choose 2} - \frac2w qh \right),$$ where $h$ is the class number of the quadratic imaginary field ${\bf Q}(\sqrt{-p})$, and $w$ is the number of roots of unity in that field, so that the factor $2/w$ is just $1$ except for $q=3$ when $2/w = 1/3$.

This is obtained by writing the sum of the residues as $\frac12 \sum_{r=1}^{p-1} (1+(r/p)) r$, where $(r/p)$ is the Legendre symbol. The $\sum_r r$ part of this gives $q \choose 2$, and the formula $-2qh/w$ for the $\sum_r (r/p) r$ part is classical (the factor $2/w$ arises via the Dirichlet class number formula, see for instance the $d<0$ part of equation (2) in MathWorld's "Class Number" page).

[The formula for $q \equiv 1 \bmod 4$ is simple because in that case the identity $(r/p) = (-r/p) = ((p-r)/p)$ yields $\sum_{r=1}^{p-1} (r/p) r = 0$ by symmetry.]

• Thank you very much! Very helpful! – Tom Mosher Nov 7 '13 at 17:52

This is a comment too long to fit in the usual format. For any $k$, denote by $r_k$ the remainder of the division of $k^2$ by $q$. Then , the sum we are considering is $S=\displaystyle\sum_{k=1}^{2b+1} r_k$, where $b$ is defined by $q=4b+3$. Leaving aside the case $q=3$, we see that $b$ cannot be divisible by $3$.

Note that modulo $q$, one has

$$S =\sum_{k=1}^{2b+1} r_k \equiv \sum_{k=1}^{2b+1} k^2 =\frac{(2b+1)(2b+2)(4b+3)}{6}=q \frac{(b+1)(2b+1)}{3} \equiv 0 \ ({\sf mod}\ q).$$

So $S$ is a multiple of $q$. If we put $T=\frac{S}{q}$, there seems to be no simple formula for $T$.

• Thank you very much for the comment! – Tom Mosher Nov 7 '13 at 17:52