Finding the Value of $\sum\limits_{n=1}^{p-1} [\sqrt{np} \ ]$

How does one find the value of the sum : $$\sum\limits_{n=1}^{p-1} [\sqrt{np} \ ]$$ where $p$ is a prime such that $p \equiv 1 (\text{mod} \ 4)$.

If i remember correctly, i got this sometime back, when i was an undergrad.

-

If you don't feel like thinking too much, here are all the details for Robin's answer...

Let's begin with the formula $\lfloor\sqrt{np}\rfloor = \sharp[C \geq 1 : np \geq C^2]$. Therefore the original sum is equal to $\sharp[n < p, C \geq 1 : np \geq C^2]$. Now we can change the order of summation to $\sum_{C=1}^{p-1} (p - \lceil C^2/p \rceil)$.

Next, we have $\lceil C^2/p \rceil = C^2/p + (-C^2 \mod p)/p$. Substituting, the sum reduces to $\sum_{C=1}^{p-1} (p - C^2/p) - \sum_{C=1}^{p-1} (-C^2 \mod p)/p$. We can calculate the first summand explicitly using the formula for sum of squares as $p(p-1) - (p-1)(2p-1)/6 = (p-1)(4p+1)/6$.

In order to calculate the second summand, notice that we are summing over all quadratic residues, twice ($-1$ is a square for our $p$). Since $p \equiv 1 \pmod{4}$, the sum of all quadratic residues equals the sum of all quadratic non-residues, and so the second summand is $-\sum_{k=1}^{p-1} k/p = -(p-1)/2$.

Putting it all together, we get $(p-1)(4p+1)/6 - (p-1)/2 = (p-1)(2p-1)/3$.

In case you were wondering, if $p$ were a prime of the other residue class, then the answer would depend on some class number.

-
This is the number of pairs $(a,b)$ of integers with $0 < a < p$, $b > 0$ and $b^2 < ap$. Reversing the implied summation gives $\sum_{b=1}^{p-1}(p-1-\lfloor b^2/p\rfloor)$. This will reduce to summing the fractional parts of $b^2/p$, which I'll leave you to think about.