Peter wrote: Let $p=4k+1$ be a prime. Show that $$ \sum^{k}_{i=1} \left \lfloor \sqrt{ ip } \right \rfloor = \frac{p^2 -1}{12}. $$ A convention first: If $\mathcal{A}$ is an assertion, then we denote by $\left[ \mathcal{A}\right] $ the logical value of the assertion $\mathcal{A}$, defined by $\left[ \mathcal{A}\right] =\left\{ \begin{array}{c} 1\text{, if }\mathcal{A}\text{ is true};\\ 0\text{, if }\mathcal{A}\text{ is false}\end{array} \right. $. Then, if $X$ is a set and $Y$ is a finite subset of $X$, then the number of elements of $Y$ equals $\left\vert Y\right\vert =\sum_{x\in X}\left[ x\in Y\right] $. This equation makes sense even if $X$ is an infinite set, because the sum $\sum_{x\in X}\left[ x\in Y\right] $ may have infinitely many terms, but only finitely many of them are nonzero - namely, those corresponding to $x$ being element of $Y$ (and $Y$ has finitely many elements). Let $\mathbb{N}$ denote the set $\left\{1,2,3,\ldots\right\}$. Let $u$ be a nonnegative real. Applying the equation $\left\vert Y\right\vert =\sum_{x\in X}\left[ x\in Y\right] $ to $X=\mathbb{N}$ and $Y=\left\{ t\in\mathbb{N}\mid t\leq u\right\} $, we see that $\left\vert \left\{ x\in\mathbb{N}\mid x\leq u\right\} \right\vert =\sum_{x\in\mathbb{N}}\left[ x\in\left\{ t\in\mathbb{N}\mid t\leq u\right\} \right] $. This simplifies to $\left\vert \left\{ x\in\mathbb{N}\mid x\leq u\right\} \right\vert =\sum_{x\in\mathbb{N}}\left[ x\leq u\right] $. But since $u$ is nonnegative, $\left\vert \left\{ x\in\mathbb{N}\mid x\leq u\right\} \right\vert =\left\lfloor u\right\rfloor $. Thus, we have proven that (1) $\left\lfloor u\right\rfloor =\sum_{x\in\mathbb{N}}\left[ x\leq u\right] $ for every nonnegative real $u$. Thus, for each integer $i$ with $1\leq i\leq k$, we have (2) $\left\lfloor \sqrt{ip}\right\rfloor =\sum_{x\in\mathbb{N}}\left[ x\leq\sqrt{ip}\right] =\sum_{x\in\mathbb{N}}\left[ x^{2}\leq ip\right] $. Now, $i\leq k$ yields $ip\leq kp$. Hence, if $x$ is an integer such that $x\geq2k+1$, then $x^{2}\geq\left( 2k+1\right) ^{2}=4k^{2}+4k+1>4k^{2}+k=k\left( 4k+1\right) =kp\geq ip$, so that $x^{2}\leq ip$ cannot hold, and thus we have $\left[ x^{2}\leq ip\right] =0$. Thus, $\sum_{x\in\mathbb{N}}\left[ x^{2}\leq ip\right] =\sum_{x=1}^{2k}\left[ x^{2}\leq ip\right] $ (because all the terms $\left[ x^{2}\leq ip\right] $ for $x\geq2k+1$ are $=0$). Combining this with (2), we get $\left\lfloor \sqrt{ip}\right\rfloor =\sum_{x=1}^{2k}\left[ x^{2}\leq ip\right] $. Now, for any integer $x$ with $1\leq x\leq2k$, we have $\left[ x^{2}\leq ip\right] =1-\left[ x^{2}\geq ip\right] $, because the assertion $x^{2}\leq ip$ holds if and only if the assertion $x^{2}\geq ip$ does not hold (in fact, $x^{2}=ip$ cannot hold, since $x$ is coprime with $p$, because $p$ is a prime and $1\leq x\leq2k<4k+1=p$). Thus, $\left\lfloor \sqrt{ip}\right\rfloor =\sum_{x=1}^{2k}\left[ x^{2}\leq ip\right] =\sum_{x=1}^{2k}\left( 1-\left[ x^{2}\geq ip\right] \right) $ $=2k-\sum_{x=1}^{2k}\left[ x^{2}\geq ip\right] =2k-\sum_{x=1}^{2k}\left[ i\leq\frac{x^{2}}{p}\right] $ (since $x^{2}\geq ip$ is equivalent to $i\leq\frac{x^{2}}{p}$). Consequently, $\sum_{i=1}^{k}\left\lfloor \sqrt{ip}\right\rfloor =\sum_{i=1}^{k}\left( 2k-\sum_{x=1}^{2k}\left[ i\leq\frac{x^{2}}{p}\right] \right) =k\cdot2k-\sum_{i=1}^{k}\sum_{x=1}^{2k}\left[ i\leq\frac{x^{2}}{p}\right] $ $=2k^{2}-\sum_{x=1}^{2k}\sum_{i=1}^{k}\left[ i\leq\frac{x^{2}}{p}\right] $. Now, for any integer $x$ with $1\leq x\leq2k$, we have $x^{2}\leq\left( 2k\right) ^{2}=k\cdot4k<k\cdot\left( 4k+1\right) =k\cdot p$, so that $\frac{x^{2}}{p}<k$. Hence, for every integer $i$ with $i>k$, we have $\frac{x^{2}}{p}<i$ and thus $\left[ i\leq\frac{x^{2}}{p} \right] =0$. Hence, $\sum_{i=1}^{k}\left[ i\leq\frac{x^{2}}{p}\right] =\sum_{i\in\mathbb{N} }\left[ i\leq\frac{x^{2}}{p}\right] $ (because all the terms $\left[ i\leq\frac{x^{2}}{p}\right] $ for $i>k$ are $=0$). Thus, $\sum_{i=1}^{k}\left\lfloor \sqrt{ip}\right\rfloor =2k^{2}-\sum_{x=1}^{2k} \sum_{i=1}^{k}\left[ i\leq\frac{x^{2}}{p}\right] $ $=2k^{2}-\sum_{x=1}^{2k}\sum_{i\in\mathbb{N}}\left[ i\leq\frac{x^{2}} {p}\right] $ $=2k^{2}-\sum_{x=1}^{2k}\left\lfloor \frac{x^{2}}{p}\right\rfloor $ (after (1) applied to $u=\frac{x^{2}}{p}$). Since $p=4k+1$, we have $k=\frac{p-1}{4}$ and $2k=\frac{p-1}{2}$, so this becomes $\sum_{i=1}^{k}\left\lfloor \sqrt{ip}\right\rfloor =2\left( \frac{p-1} {4}\right) ^{2}-\sum_{x=1}^{\left( p-1\right) /2}\left\lfloor \frac{x^{2} }{p}\right\rfloor $. Now, according to formula (5) in http://www.mathlinks.ro/Forum/viewtopic.php?t=150712 (or http://www.problem-solving.be/pen/viewtopic.php?t=346 ), post #2, Theorem 2, we have $\sum_{x=1}^{\left( p-1\right) /2}\left\lfloor \frac{x^{2}} {p}\right\rfloor =\frac{\left( p-1\right) \left( p-5\right) }{24}$, so that $\sum_{i=1}^{k}\left\lfloor \sqrt{ip}\right\rfloor =2\left( \frac{p-1} {4}\right) ^{2}-\frac{\left( p-1\right) \left( p-5\right) } {24} =\frac{p^{2}-1}{12}$, qed. PS. This problem has been also discussed at http://www.mathlinks.ro/Forum/viewtopic.php?t=5928 . Darij