Sum of remainders of Triangular numbers

Question

Let $p=8k+7$ be a prime number, prove that:

$$\sum_{k=1}^{p-1} \left\{ \frac{2T(k)}{p}\right\} = \sum_{k=1}^{p-1} \left\{ \frac{k}{p}\right\}$$

, where $T(k)$ is the $k-$th Triangular number and $\{\frac{k}{p}\}$ is the decimal part of $\frac{k}{p}$.

---

It's fairly easy to notice that the RHS is equal to $\frac{p-1}{2}$, as all the fractions are less than 1, but I'm having troubles with the LHS. It's easy to notice that the terms are symmetric wrt the $\frac{p-1}{2}$ term, but that's all I found. I tried writing $2T(n) = n(n+1) = n^2 + n = (n+1)^2 - (n+1)$, but none of this helped me.

Also it's easy to notice that: $\{\frac{i}{p}\} = \frac{x}{p}$, where $x$ is the remainder when $i$ is divided by $p$. I tried a lot of examples, but I can't see a correlation between these numbers. Also as the sum of the $x$'s is less than $p^2$ I tried working modulo $p^2$ and proving that their sum is equal to $\frac{p(p-1)}{2}$, but again to no avail.

In fact I can't make use of the fact that $p$ is of the given form, as it seems that for primes other than those from the given form the identity doesn't hold.

Answer 1

This problem seems to be tied with how the squares are distributed when you split $\{1 \ldots p-1\}$ in $8$.

First, $2T(n) = n^2+n = (n+\frac 12)^2- \frac 14$ (remember that modulo $p$, $\frac 12 = \frac{p+1}2$ and $\frac 14 = \frac{p+1}8$).

Since every nonzero square / triangular number not equal to $-\frac 14$ is obtained twice, the difference between the two sums is the difference between the sum of the nonzero squares (translated by $-\frac 14$) and the sum of the nonsquares (also translated).

Split $(\Bbb Z/p \Bbb Z)^*$ in $8$ parts, $A_0 = \{1 \ldots \frac{p-7}8\}$,
$A_i = \{i\frac{p+1}8 \ldots (i+1)\frac{p+1}8-1\}$ for $i=1 \ldots 6$, and
$A_7 = \{7\frac{p+1}8 \ldots p-1 \}$.

$A_1$ and $A_7$ have $\frac {p-7}8$ elements, and the other $6$ have $\frac {p+1}8$ elements (so one more), for a total of $\frac{2p-14+6p+6}8 = p-1$.

Let $R_i$ be the squares residues in $A_i$, $N_i = A_i \setminus R_i$ be the nonresidues, and if $R$ if any of those sets, denote $\#S$ and $S(R)$ the cardinal and the sum (not modulo $p$) of $R$ respectively.
We have $\# R_i + \# N_i = \# A_i = (p-7)/8$ or $(p+1)/8$ according to $i$,
and $S(R_i) + S(N_i) = S(A_i)$ which can also be explicitly computed (but we won't need it)

The LHS is $- \frac 14$ plus twice the sum of the squares translated by $-\frac{p+1}4$. So if a square $s$ is in a $R_i$ for $i>1$ it contributes by $s- \frac{p+1}4$, and if it is in a $R_i$ for $i \le 1$ it contributes by $s+\frac{3p-1}4$.

And so the LHS is $\frac{3p-1}4 + 2\sum S(R_i) + (\#R_0+\#R_1)\frac{3p-1}2 - (\#R_2+\ldots+\#R_7)\frac{p+1}2$
The RHS is the sum of everyone so it is $\sum S(R_i) + \sum S(N_i)$.

---

Now, we use that $p = 7 \pmod 8$, which means in terms of squares, that $-1$ is not a square and that $2$ is a square.

Therefore, multiplication by $-1$ is a bijection between $A_i$ and $A_{7-i}$, and it switches squares with nonsquares.

This implies, about the sums, that $S(R_i) + S(N_{7-i}) = p\# R_i$ for $i=0\ldots 7$.

Summing those $8$ equations we can rewrite the RHS as $p \sum \# R_i$
Substracting it from the LHS you get their difference
$\Delta = \frac{3p-1}4 + 2\sum S(R_i) + (\#R_0+\#R_1)\frac{p-1}2 - (\#R_2+\ldots+\#R_7)\frac{3p+1}2$

As for the cardinals, we get $\# R_i = \# N_{7-i}$ for $i=0\ldots 7$.
Combining this with the knowledge about $\# A_i$, we have $\# R_0 + \# R_7 = (p-7)/8$, and $\# R_1 + \# R_6 = \# R_2 + \# R_5 = \# R_3 + \# R_4 = (p+1)/8$

---

Next, multiplication by $2$ is a bijection between $A_i \cup A_{i+4}$ and $A_{2i} \cup A_{2i+1}$ that keeps squares and nonsquares.

About the sums, we get :
$ 2S(R_i) + 2S(R_{4+i})-p\#R_{4+i} = S(R_{2i}) + S(R_{2i+1})$ for $i=0 \ldots 3$

Summing those $4$ equations gives $\sum S(R_i) = p (\# R_4 + \ldots + \#R_7)$

Plugging this in $\Delta$ we get $\Delta = \frac{3p-1}4 + (\#R_0+\#R_1+\#R_4+ \ldots + \#R_7)\frac{p-1}2 - (\#R_2+\#R_3)\frac{3p+1}2 $

Now, for cardinals, we get $\# R_i + \# R_{4+i} = \# R_{2i} + \# R_{2i+1}$ for $i=0 \ldots 3$, which can be summarized as $\#R_1 = \#R_4, \#R_2 + \#R_3 = \#R_4 + \#R_5, \#R_6 = \# R_3$

Using the previous equations we obtain $\#R_1 = \# R_2 = \#R_4$ and $\# R_3 = \# R_5 = \# R_6$, (and that the sum of those two quantities is $\frac{p+1}8$)

And so $\Delta = \frac{3p-1}4 + ((\#R_0+\#R_7)+2(\#R_1+\#R_3))\frac{p-1}2 - (\#R_1+\#R_3)\frac{3p+1}2 $
$= \frac{3p-1}4 + (\#R_0+\#R_7)\frac{p-1}2 - (\#R_1+\#R_3)\frac{p+3}2 $
$= \frac{3p-1}4 + \frac{(p-7)(p-1)}{16} - \frac{(p+1)(p+3)}{16}$
$= \frac{3p-1}4 + \frac{-12p+4}{16} = 0$

Answer 2

Let $p$ be a prime number then $$\sum_{k=1}^{p-1} \left\{ \frac{k^2+k}{p}\right\} = \frac{1}{p}\sum_{j=1}^{p-1} j\left({4j+1\over p}\right)+\frac{p-1}{2}.$$ In fact, let $r_n(m)$ be the remainder of the division of $m$ by $n$ then $$\sum_{k=1}^{p-1} \left\{ \frac{k^2+k}{p}\right\} ={1\over p}\sum_{k=1}^{p-1} r_p(k^2+k)$$ Note that $r_p(k^2+k)=j$ for some $j\in\{1,\dots,p-1\}$ iff $k^2+k=j$ (mod $p$), that is iff $\Delta=1+4j$ is a square modulo $p$ iff $\left({4j+1\over p}\right)=1$ where $\left({\cdot \over p}\right)$ is the Legendre symbol. Therefore the number of $k\in\{1,\dots,p-1\}$ such that $r_p(k^2+k)=j$ is $\left(\left({4j+1\over p}\right)+1\right)$ (it gives $0$ or $2$) and $$\sum_{k=1}^{p-1} r_p(k^2+k)= \sum_{j=1}^{p-1} j\left(\left({4j+1\over p}\right)+1\right)= \sum_{j=1}^{p-1} j\left({4j+1\over p}\right)+\frac{p^2-p}{2}. $$

Now let us assume that $p$ is congruent to 7 modulo 8. By the above formula, in order to prove the proposed problem, it suffices to show that $$S_1=\sum_{j=0}^{p-1} j\left({4j+1\over p}\right)=0.$$

Let \begin{align*} &A=\sum_{j=0}^{p-1} j\left({j\over p}\right), \ \ \ \ \ \ \ B=\sum_{j=0}^{p-1} \left({j\over p}\right),\\ &U_i=\sum_{j=0}^{p-1} j\left({2j+i\over p}\right), V_i=\sum_{j=0}^{p-1} \left({2j+i\over p}\right) \mbox{for $i=0,1$},\\ &S_i=\sum_{j=0}^{p-1} j\left({4j+i\over p}\right), T_i=\sum_{j=0}^{p-1} \left({4j+i\over p}\right) \mbox{for $i=0,1,2,3$}. \end{align*} Then $B=V_i=T_i=0$ because $p$ does not divide $2$ and $4$ (see this). Moreover $p\equiv 7$ (mod $8$) implies $$\left({-1\over p}\right)=(-1)^{(p-1)/2}=-1\quad\mbox{and}\quad \left({2\over p}\right)=(-1)^{\lfloor(p+1)/4\rfloor}=1.$$ Now, $U_0=S_0=A$ and \begin{align*} \sum_{r=0}^{2p-1} r\left({r\over p}\right)&= \sum_{i=0}^1\sum_{j=0}^{p-1}(2j+i)\left({2j+i\over p}\right) =2U_0+2U_1+V_1=2A+2U_1,\\ \sum_{r=0}^{2p-1} r\left({r\over p}\right)&= \sum_{i=0}^1\sum_{r=0}^{p-1} (ip+r)\left({ip+r\over p}\right) =A+pB+A=2A, \end{align*} which imply that $S_2=U_1=0$. Moreover \begin{align*} \sum_{r=0}^{4p-1} r\left({r\over p}\right)&= \sum_{i=0}^3\sum_{j=0}^{p-1}(4j+i)\left({4j+i\over p}\right) =4S_0+4S_1+4S_2+4S_3+T_1+T_2+T_3=4A+4S_1+4S_3,\\ \sum_{r=0}^{4p-1} r\left({r\over p}\right)&= \sum_{i=0}^3\sum_{r=0}^{p-1} (ip+r)\left({ip+r\over p}\right) =A+pB+A+2pB+A+3pB+A=4A, \end{align*} which imply that $S_1+S_3=0$. Finally \begin{align*} S_1 &=\sum_{j=1}^{p-1} j\left({4j+1\over p}\right) =\sum_{j=1}^{p-1} (p-j)\left({4(p-j)+1\over p}\right) =-p\sum_{j=1}^{p-1}\left({4j-1\over p}\right) +\sum_{j=1}^{p-1}j\left({4j-1\over p}\right)\\ &=-(p-1)\sum_{j=0}^{p-2}\left({4j+3\over p}\right) +\sum_{j=0}^{p-2}j\left({4j+3\over p}\right)\\ &=(p-1)\left({-1\over p}\right)-(p-1)T_3-(p-1)\left({-1\over p}\right)+S_3=S_3 \end{align*} and we obtain that $S_1=S_3=0$.