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?

  • 2
    $\begingroup$ It's perfectly correct to call $p=7+8t$ (for integer $t$ of course). That's the definition of $\mathrm{mod}$. $\endgroup$ – EuYu Oct 8 '13 at 7:16
  • $\begingroup$ The problem is $t$ is not true for all integers $\endgroup$ – Aloginame Oct 8 '13 at 22:43
  • $\begingroup$ obviously not, but given $p,$ such a $t$ exists. $\endgroup$ – cats Oct 8 '13 at 22:48
  • $\begingroup$ 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. $\endgroup$ – EuYu Oct 8 '13 at 22:57
  • $\begingroup$ oh never thought of it like that but isn't that no good for $n(n+1) > p$? $\endgroup$ – 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)$$

  • $\begingroup$ 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. $\endgroup$ – 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}$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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