Peter wrote: Let $ p$ be a prime number of the form $ 4k + 1$. Show that \[ \sum^{p - 1}_{i = 1}( \lfloor \frac {2i^{2}}{p} \rfloor - 2 \lfloor \frac {i^{2}}{p} \rfloor ) = \frac {p - 1}{2}. \] Lemma 1 from http://www.mathlinks.ro/Forum/viewtopic.php?t=150711 (or http://www.problem-solving.be/pen/viewtopic.php?t=345 ) states: Lemma 1. For any integer $ n$ and any non-integer real number $ a$, we have $ \lfloor a \rfloor + \lfloor n - a \rfloor = n - 1$. Now, since $ p$ is a prime number of the form $ 4k + 1$, it is known that $ - 1$ is a quadratic residue modulo $ p$. Thus, there exists an integer $ \lambda$ such that $ \lambda^{2}\equiv - 1\text{ mod }p$. Now, $ p\nmid\lambda$ (because else, we would have $ \lambda^{2}\equiv 0\text{ mod }p$, contradicting $ \lambda^{2}\equiv - 1\text{ mod }p$). Therefore, multiplication with $ \lambda$ is a permutation of the nonzero residues modulo $ p$. In other words, if we define a function $ L$ from $ \{1;\;2;\;...;\;p - 1\}$ to $ \{1;\;2;\;...;\;p - 1\}$ by letting $ L(i)$ be the remainder of $ \lambda i$ upon division by $ p$ for every $ i\in\{1;\;2;\;...;\;p - 1\}$, then this function $ L$ is a permutation of $ \{1;\;2;\;...;\;p - 1\}$. Thus, (1) $ \sum^{p - 1}_{i = 1}( \lfloor \frac {2i^{2}}{p} \rfloor - 2 \lfloor \frac {i^{2}}{p} \rfloor ) = \sum^{p - 1}_{i = 1}( \lfloor \frac {2(L(i))^{2}}{p} \rfloor - 2 \lfloor \frac {(L(i))^{2}}{p} \rfloor )$. Now, for every $ i\in\{1;\;2;\;...;\;p - 1\}$, both integers $ i^{2}$ and $ 2i^{2}$ are coprime with $ p$ (since $ i$ is coprime with $ p$ because $ p$ is a prime and $ 1\leq i < p$, and $ 2$ is coprime with $ p$ because $ p$ has the form $ 4k + 1$ and is therefore odd). We have defined $ L(i)$ as the remainder of $ \lambda i$ upon division by $ p$; thus, $ L(i)\equiv\lambda i\text{ mod }p$, and therefore, $ i^{2} + (L(i))^{2}\equiv i^{2} + (\lambda i)^{2} = (1 + \lambda^{2})i^{2}\equiv(1 + ( - 1))i^{2} = 0i^{2} = 0\text{ mod }p$. Hence, $ \frac {i^{2} + (L(i))^{2}}{p}$ is an integer. On the other hand, $ \frac {i^{2}}{p}$ is a non-integer (since $ i^{2}$ is coprime with $ p$). Thus, applying Lemma 1 to $ n = \frac {i^{2} + (L(i))^{2}}{p}$ and $ a = \frac {i^{2}}{p}$, we obtain $ \lfloor\frac {i^{2}}{p}\rfloor + \lfloor\frac {i^{2} + (L(i))^{2}}{p} - \frac {i^{2}}{p}\rfloor = \frac {i^{2} + (L(i))^{2}}{p} - 1$. Equivalently, (2) $ \lfloor\frac {i^{2}}{p}\rfloor + \lfloor\frac {(L(i))^{2}}{p}\rfloor = \frac {i^{2}}{p} + \frac {(L(i))^{2}}{p} - 1$. On the other hand, $ 2\cdot \frac {i^{2} + (L(i))^{2}}{p}$ is an integer (since $ \frac {i^{2} + (L(i))^{2}}{p}$ is an integer), while $ \frac {2i^{2}}{p}$ is a non-integer (since $ 2i^{2}$ is coprime with $ p$). Thus, applying Lemma 1 to $ n = 2\cdot\frac {i^{2} + (L(i))^{2}}{p}$ and $ a = \frac {2i^{2}}{p}$, we obtain $ \lfloor\frac {2i^{2}}{p}\rfloor + \lfloor 2\cdot\frac {i^{2} + (L(i))^{2}}{p} - \frac {2i^{2}}{p}\rfloor = 2\cdot\frac {i^{2} + (L(i))^{2}}{p} - 1$. Equivalently, (3) $ \lfloor\frac {2i^{2}}{p}\rfloor + \lfloor\frac {2(L(i))^{2}}{p}\rfloor = \frac {2i^{2}}{p} + \frac {2(L(i))^{2}}{p} - 1$. Now, $ \sum^{p - 1}_{i = 1}( \lfloor \frac {2i^{2}}{p} \rfloor - 2 \lfloor \frac {i^{2}}{p} \rfloor ) = \frac12\cdot(\sum^{p - 1}_{i = 1}( \lfloor \frac {2i^{2}}{p} \rfloor - 2 \lfloor \frac {i^{2}}{p} \rfloor ) + \sum^{p - 1}_{i = 1}( \lfloor \frac {2i^{2}}{p} \rfloor - 2 \lfloor \frac {i^{2}}{p} \rfloor ))$ $ = \frac12\cdot(\sum^{p - 1}_{i = 1}( \lfloor \frac {2i^{2}}{p} \rfloor - 2 \lfloor \frac {i^{2}}{p} \rfloor ) + \sum^{p - 1}_{i = 1}( \lfloor \frac {2(L(i))^{2}}{p} \rfloor - 2 \lfloor \frac {(L(i))^{2}}{p} \rfloor ))$ (from (1)) $ = \frac12\cdot\sum^{p - 1}_{i = 1}( \lfloor \frac {2i^{2}}{p} \rfloor - 2 \lfloor \frac {i^{2}}{p} \rfloor + \lfloor \frac {2(L(i))^{2}}{p} \rfloor - 2 \lfloor \frac {(L(i))^{2}}{p} \rfloor )$ $ = \frac12\cdot\sum^{p - 1}_{i = 1}( ( \lfloor \frac {2i^{2}}{p} \rfloor + \lfloor \frac {2(L(i))^{2}}{p} \rfloor ) - 2 ( \lfloor \frac {i^{2}}{p} \rfloor + \lfloor \frac {(L(i))^{2}}{p} \rfloor ))$ $ = \frac12\cdot\sum^{p - 1}_{i = 1}( (\frac {2i^{2}}{p} + \frac {2(L(i))^{2}}{p} - 1) - 2(\frac {i^{2}}{p} + \frac {(L(i))^{2}}{p} - 1))$ (according to (3) and (2)) $ = \frac12\cdot\sum^{p - 1}_{i = 1}1 = \frac12\cdot(p - 1) = \frac {p - 1}{2}$, qed. Using the above, we can also show: Theorem 2. If $ p$ is a prime of the form $ 4k + 1$, then (4) $ \sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \frac {(p - 1)(p - 2)}{3}$; (5) $ \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \frac {(p - 1)(p - 5)}{24}$; (6) $ \sum^{p - 1}_{i = (p + 1)/2} \lfloor \frac {i^{2}}{p} \rfloor = \frac {(p - 1)(7p - 11)}{24}$. Proof of Theorem 2. Since $ L$ is a permutation of $ \{1;\;2;\;...;\;p - 1\}$, we have (7) $ \sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \sum^{p - 1}_{i = 1} \lfloor \frac {(L(i))^{2}}{p} \rfloor$ and (8) $ \sum^{p - 1}_{i = 1}\frac {i^{2}}{p} = \sum^{p - 1}_{i = 1}\frac {(L(i))^{2}}{p}$. Thus, $ \sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \frac12\cdot(\sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor)$ $ = \frac12\cdot(\sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \sum^{p - 1}_{i = 1} \lfloor \frac {(L(i))^{2}}{p} \rfloor)$ (from (7)) $ = \frac12\cdot\sum^{p - 1}_{i = 1}( \lfloor \frac {i^{2}}{p} \rfloor + \lfloor \frac {(L(i))^{2}}{p} \rfloor)$ $ = \frac12\cdot\sum^{p - 1}_{i = 1}(\frac {i^{2}}{p} + \frac {(L(i))^{2}}{p} - 1)$ (according to (2)) $ = \frac12\cdot(\sum^{p - 1}_{i = 1}\frac {i^{2}}{p} + \sum^{p - 1}_{i = 1}\frac {(L(i))^{2}}{p} - (p - 1))$ $ = \frac12\cdot(\sum^{p - 1}_{i = 1}\frac {i^{2}}{p} + \sum^{p - 1}_{i = 1}\frac {i^{2}}{p} - (p - 1))$ (according to (8)) $ = \frac12\cdot(2\sum^{p - 1}_{i = 1}\frac {i^{2}}{p} - (p - 1)) = \sum^{p - 1}_{i = 1}\frac {i^{2}}{p} - \frac {p - 1}{2} = \frac {1}{p}\cdot\sum^{p - 1}_{i = 1}i^{2} - \frac {p - 1}{2}$ $ = \frac {1}{p}\cdot\frac {(p - 1)((p - 1) + 1)(2(p - 1) + 1)}{6} - \frac {p - 1}{2} = \frac {(p - 1)(p - 2)}{3}$. This proves (4). Now, $ \sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \sum^{p - 1}_{i = (p + 1)/2} \lfloor \frac {i^{2}}{p} \rfloor$. On the other hand, $ \sum^{p - 1}_{i = (p + 1)/2} \lfloor \frac {i^{2}}{p} \rfloor = \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {(p - i)^{2}}{p} \rfloor$ (this is just an index substitution: $ i\mapsto p - i$), so this rewrites as $ \sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {(p - i)^{2}}{p} \rfloor$. Now, for any integer $ i$, we have $ \frac {(p - i)^{2}}{p} = \frac {i^{2}}{p} + (p - 2i)$. Since $ p - 2i$ is an integer, this yields $ \lfloor \frac {(p - i)^{2}}{p} \rfloor = \lfloor \frac {i^{2}}{p} \rfloor + (p - 2i)$, and thus $ \sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {(p - i)^{2}}{p} \rfloor$ $ = \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \sum^{(p - 1)/2}_{i = 1}( \lfloor \frac {i^{2}}{p} \rfloor + (p - 2i))$ $ = \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + (\sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \frac {p - 1}{2}p - 2\cdot\sum^{(p - 1)/2}_{i = 1}i)$ $ = 2\sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \frac {p - 1}{2}p - 2\cdot\sum^{(p - 1)/2}_{i = 1}i)$ $ = 2\sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \frac {p - 1}{2}p - 2\cdot\frac {\frac {p - 1}{2}(\frac {p - 1}{2} + 1)}{2}$. Thus, the equation (4) rewrites as $ 2\sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor + \frac {p - 1}{2}p - 2\cdot\frac {\frac {p - 1}{2}(\frac {p - 1}{2} + 1)}{2} = \frac {(p - 1)(p - 2)}{3}$. Thus, $ 2\sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \frac {(p - 1)(p - 2)}{3} - \frac {p - 1}{2}p + 2\cdot\frac {\frac {p - 1}{2}(\frac {p - 1}{2} + 1)}{2} = \frac {(p - 1)(p - 5)}{12}$, so that $ \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \frac {(p - 1)(p - 5)}{24}$, and (5) is proven. Now, (4) and (5) yield $ \sum^{p - 1}_{i = (p + 1)/2} \lfloor \frac {i^{2}}{p} \rfloor = \sum^{p - 1}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor - \sum^{(p - 1)/2}_{i = 1} \lfloor \frac {i^{2}}{p} \rfloor = \frac {(p - 1)(p - 2)}{3} - \frac {(p - 1)(p - 5)}{24}$ $ = \frac {(p - 1)(7p - 11)}{24}$, and this proves (6). Thus, Theorem 2 is verified. Darij

Peter wrote: Let $ p$ be a prime number of the form $ 4k + 1$. Show that \[ \sum^{p - 1}_{i = 1}\left( \left \lfloor \frac {2i^{2}}{p}\right \rfloor - 2\left \lfloor \frac {i^{2}}{p}\right \rfloor \right) = \frac {p - 1}{2}. \] Let $ \{x\}=x-[x] \in (0;1)$ Wirting $ [\frac{2i^2}{p}]=\frac{2i^2}{p}-\{\frac{2i^2}{p}\}$ and $ [\frac{i^2}{p}]=\frac{i^2}{p}-\{\frac{i^2}{p}\}$ We find that $ [\frac{2i^2}{p}]-2[\frac{i^2}{p}]=2\{\frac{i^2}{p}\}-\{\frac{2i^2}{p}\}$ When $ \{x\} <\frac{1}{2};2\{x\}-\{2x\}=2\{x\}-2\{x\}=0$ When $ \{x\}>\frac{1}{2};2\{x\}-\{2x\}=2\{x\}-(2\{x\}-1)=1$ Therefore,the desired sum equals the number $ \alpha$ of $ i$ in $ [1;p-1]$ such that $ \{\frac{i^2}{p}\} \geq \frac{1}{2}$,or equivalently,the number of nonzoro residue $ i$ modulo $ p$ such that $ i^2$is congruent to some number in $ [\frac{p+1}{2};p-1]$ modulo $ p$ $ p$ is a prime congruent to $ 1$ modulo $ 4$ ,it is well known that $ -1 \equiv d^2(mod p)$ for some integer $ d$ Partition the nonzero residues modulo $ p$ into $ \frac{p-1}{2}$ pairs of the form $ \{a;da\}$,so that $ a^2 \equiv (-da)^2(mod p)$ in each pair Thus,exactly one residue in each pair has a square congruent to some number in $ [\frac{p+1}{2};p-1]$,for a total of $ \frac{p-1}{2}$ such residues,It follows that the given sum equals $ \frac{p-1}{2}$,are desired.

Peter wrote: Let $ p$ be a prime number of the form $ 4k + 1$. Show that \[ \sum^{p - 1}_{i = 1}\left( \left \lfloor \frac {2i^{2}}{p}\right \rfloor - 2\left \lfloor \frac {i^{2}}{p}\right \rfloor \right) = \frac {p - 1}{2}. \] It is obviosly, because $ f(i) = [\frac {2i^2}{p}] - 2[\frac {i^2}{p}] = \theta(\{\frac {i^2}{p}\} - \frac 12)$, were $ \theta(x) = 0$ if $ x\le 0$ and $ \theta(x) = 1$ if $ x > 0$. Let $ j^2 = - 1\mod p$, then the set 4k residius can be represented as k sets $ \{i,ij,p - i,p - ij\}$ and $ f(i) + f(ij) = 1,f(p - i) + f(p - ij) = 1$, therefore $ \sum_i f(i) = 2k = \frac {p - 1}{2}.$

https://artofproblemsolving.com/community/c6h36566p230042