Proof that:$\sum\limits_{n=1}^{p} \left\lfloor \frac{n(n+1)}{p} \right\rfloor= \frac{2p^2+3p+7}{6}$ where $p$ is a prime and $p \equiv 7 \mod{8}$

Proof that:$\sum\limits_{n=1}^{p} \left\lfloor \frac{n(n+1)}{p} \right\rfloor= \frac{2p^2+3p+7}{6}$
where $p$ is a prime number such that $p \equiv 7 \mod{8}$

I tried to separate the sum into parts but it does not seems to go anywhere. I also tried to make a substitutions for $p$ ,but, I don't think it is entriely correct to call $p=7+8t$. Any ideas?

• It's perfectly correct to call $p=7+8t$ (for integer $t$ of course). That's the definition of $\mathrm{mod}$. – EuYu Oct 8 '13 at 7:16
• The problem is $t$ is not true for all integers – Aloginame Oct 8 '13 at 22:43
• obviously not, but given $p,$ such a $t$ exists. – cats Oct 8 '13 at 22:48
• An equivalent formulation of this problem is to the find the sum of the residues $n(n+1)\pmod p$, i.e. to find the value of $$\sum_{n=1}^p[n(n+1)\pmod p]$$ Not too sure whether it is easier to work with the floors directly or to try this alternate approach. – EuYu Oct 8 '13 at 22:57
• oh never thought of it like that but isn't that no good for $n(n+1) > p$? – Aloginame Oct 8 '13 at 23:05

$$\sum_{i=1}^p \frac{n(n+1)}p = \frac1 p \frac {p(p+1)(p+2)}3 = \frac{p^2+3p+2}3$$, and $$\frac{p^2+3p+2}3 - \frac{2p^2+3p+7}6 = \frac{p-1}2$$

So you are asking to prove that $$\sum_{n=1}^p \frac{n(n+1)}p - \lfloor\frac{n(n+1)}p\rfloor = \frac{p-1}2$$.

The term being summed is $\dfrac 1 p$ times the residue of $n(n+1)$ modulo $p$. So this becomes showing $\displaystyle \sum_{n \in \Bbb F_p} (n(n+1) \pmod p) = p(p-1)/2$

Let $f(x)$ be the number of solutions to $n(n+1)=x$ in $\Bbb F_p$. $n(n+1) = x \iff n^2 + n = x \iff (2n+1)^2 = 4x+1$, hence $\displaystyle f(x) = 1 + \binom{4x+1}p$,

and the sum becomes $\displaystyle \sum_{x=0}^{p-1} x f(x) = \sum x + \sum x \binom{4x+1}p$.
The first sum is $p(p-1)/2$, so we are left with showing that the second sum is zero.

Let us do a last rearrangement by setting $y = 1+4x$ and writing the sum as $\displaystyle \sum x(y) \binom y p$, where $x(y) = \frac 14 (y-1 + k(y)p)$ and $k(y)$ is the remainder of $y-1$ mod $4$.

Let $\displaystyle S_i = \sum_{y \equiv i \pmod 4} \binom y p$.
Since $-1$ is not a square, $S_0 = - S_3$ and $S_1 = - S_2$.
Since $2$ is a square, $S_1 + S_3 = S_2 + S_3$ (and $S_0 + S_2 = S_0 + S_1$) hence $S_1 = S_2 = 0$.

We can rewrite the sum into $$\frac 1 4 \left(\sum y\binom y p + (3p-1)S_0 - S_1 + (p-1)S_2 + (2p-1)S_3\right) = \frac 1 4 \left(\sum y\binom y p + p(S_0 + S_2)\right)$$

Since $(-1)$ is not a square, $$\sum y \binom y p = \sum_0^{(p-1)/2} (2y - p) \binom y p$$ By this question, this is $$-p \sum_0^{(p-1)/2} \binom y p = -p \sum_0^{(p-1)/2} \binom {2y} p = -p(S_0 + S_2)$$

• If you deleted this answer because the question was from an AMM problem, note that the submission deadline has passed, so it's probably safe to undelete. – user642796 Mar 15 '14 at 4:25

This is a partial answer. By the division algorithm let $n(n+1) = q_n p + r_n$ where $0\leq r_n < p$. Then we see that

$$\left\lfloor\frac{n(n+1)}{p}\right\rfloor = \left\lfloor q_n + \frac{r_n}{p}\right\rfloor = q_n + \left\lfloor\frac{r_n}{p}\right\rfloor = q_n$$

So the problem transforms into finding the sum of the quotients $q_n$. Here

$$\sum_{n=1}^p q_n =\sum_{n=1}^p\frac{n(n+1) - r_n}{p} = \frac{1}{3}(p+1)(p+2) - \frac{1}{p} \sum_{n=1}^p r_n$$

Now compare this to what we need to obtain. We transformed this problem into the following one. Let $p \equiv 7 \pmod{8}$. Show that

$$\sum_{n=1}^p r_n = \frac{p(p-1)}{2}$$

where $r_n$ is the equivalence class of $n(n+1)$ modulo $p$. This I believe is an easier problem. The last two residues are $0$ so you have to show

$$\sum_{n=1}^{p-2} r_n = \frac{p(p-1)}{2}$$

• This is precisely what I mentioned in the comments. I'm not sure if this approach actually is easier. – EuYu Oct 10 '13 at 9:57
• Oh I didn't realize – Alexander Vlasev Oct 10 '13 at 9:58