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.]

  • $\begingroup$ Thank you very much! Very helpful! $\endgroup$ – 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$.

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

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.