Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that $\lfloor \sqrt{p} \rfloor + \lfloor \sqrt{2p} \rfloor +...+ \lfloor \sqrt{\frac{p-1}{4}p} \rfloor = \dfrac{p^2 - 1}{12}$ where $p$ prime such that $p \equiv 1 \pmod{4}$.

I really have no idea how to start :(! The square root part really messed me up. Can anyone give me a hint?

Thank you

share|cite|improve this question
Although the notation is suggestive, you need to add the assumption explicitly that $p$ is prime. – Douglas Zare Apr 4 '11 at 4:59
@Douglas Zare: Thanks for pointing that out. – Chan Apr 4 '11 at 5:05
maybe this could help - the left side counts the number of triples (x,a,n) such that $0<x<p,\; 0<a\leq \frac{p-1}{4}p,\; n\geq 0$ and $x^2+np=a$. For $n=k$ there are exactly $\lfloor \sqrt{(\frac{p-1}{4}-k)p} \rfloor$ solutions. I don't know what to do with the other side or where $p\equiv 1 (4)$ comes in. – Prometheus Apr 4 '11 at 6:25
Related: In fact, possible candidate for dupe...… – Aryabhata Apr 4 '11 at 16:30
up vote 16 down vote accepted

The sum $S(p)$ counts the lattice points with positive coordinates under $y=\sqrt{px}$ from $x=1$ to $x=\frac{p-1}{4}$. Instead of counting the points below the parabola, we can count the lattice points on the parabola and above the parabola, and subtract these from the total number of lattice points in a box. Stop here if you only want a hint.

Since $p$ is prime, there are no lattice points on that parabola (with that range of $x$ values).

The total number of lattice points in the box $1 \le x \le \frac{p-1}4, 1\le y \le \frac {p-1}2$ is $\frac{(p-1)^2}8$.

The lattice points above the parabola are to the left of the parabola. These are counted by $T(p)= \lfloor 1^2/p \rfloor + \lfloor 2^2/p \rfloor + ... + \lfloor (\frac{p-1}2)^2/p \rfloor$.

$T(p)+S(p) = \frac{(p-1)^2}8$, so $S = \frac {p^2-1}{12}$ is equivalent to $T(p) = \frac{(p-1)(p-5)}{24}$.

Consider $T(p)$ without the floor function. This sum is elementary:

$$\sum_{i=1}^{(p-1)/2} \frac{i^2}p = \frac 1p \sum_{i=1}^{(p-1)/2} i^2 = \frac 1p \frac 16 (\frac{p-1}2)(\frac {p-1}2 + 1)(2\frac{p-1}2 +1) = (p^2-1)/24.$$

What is the difference between these? Abusing the mod notation, $\frac{i^2}p - \lfloor \frac{i^2}p \rfloor = 1/p \times (i^2 \mod p)$. So,

$$(p^2-1)/24 - T(p) = \sum_{i=1}^{(p-1)/2} \frac{i^2}p - \lfloor \frac{i^2}p \rfloor = \sum_{i=1}^{(p-1)/2} \frac 1p \times (i^2 \mod p) = \frac 1p \sum_{i=1}^{(p-1)/2} (i^2 \mod p).$$

Since $i^2 = (-i)^2$, this last sum is over the nonzero quadratic residues. Since $p$ is $1 \mod 4$, $-1$ is a quadratic residue, so if $a$ is a nonzero quadratic residue, then so is $p-a$. Thus, the nonzero quadratic residues have average value $p/2$ and the sum is $\frac{(p-1)}2 \frac p2$.

$$(p^2-1)/24 - T(p) = \frac 1p \frac{(p-1)}2 \frac p2 = \frac{p-1}4$$ $$T(p) = \frac{(p-1)(p-5)}{24}.$$

That was what we needed to show.

share|cite|improve this answer
Many thanks. It's much more complicated than I initially thought. – Chan Apr 4 '11 at 23:06
It is easier if you notice that your question here is a step in this calculation. Are these from the same source? – Douglas Zare Apr 4 '11 at 23:40
Yes, they are. You have a very sharp eyes ;)! I'm amazed. – Chan Apr 4 '11 at 23:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.