Given that $\sum_{k=1}^n \lfloor \sqrt{k} \rfloor = Nn-\frac{N(N-1)(2N+5)}{6}$ where $N=\lfloor \sqrt{n} \rfloor$, for which values of N is the sum $\sum_{k=1}^n \lfloor \sqrt{k} \rfloor$ divisible by N?
Sum of a floor function
1 Answers
The question amounts to asking for what values of $N$ the expression $Nn-\frac{N(N-1)(2N+5)}{6}$ is divisible by $N$. Since $Nn$ is certainly divisible by $N$, this is the same as asking when $\frac{N(N-1)(2N+5)}{6}=N\cdot\frac{(N-1)(2N+5)}6$ is divisible by $N$. Clearly this is the case precisely when $(N-1)(2N+5)$ is divisible by $6$.
A number is divisible by $6$ if and only if it’s divisible by both $2$ and $3$. $2N+5$ is always odd, so it’s never divisible by $2$. Thus, $(N-1)(2N+5)$ is divisible by $2$ if and only if $N-1$ is even, i.e., if and only if $N$ is odd. Thus, $N$ must be congruent to $1,3$, or $5\bmod 6$. If $N\equiv 3\pmod 6$, then $(N-1)(2N+5)\equiv 2\cdot5\equiv 4\pmod 6\;,$ so $(N-1)(2N+5)$ is not divisible by $6$. If $N\equiv 1\pmod 6$, $(N-1)(2N+5)\equiv 0\pmod 6\;,$ so $(N-1)(2N+5)$ is certainly divisible by $6$. And if $N\equiv 5\pmod 6$, then $(N-1)(2N+5)\equiv 4\cdot3\equiv 0\pmod 6\;,$ and again $(N-1)(2N+5)$ is divisible by $6$.
Thus, $(N-1)(2N+5)$ is divisible by $6$ if and only if $N\equiv 1\pmod 6$ or $N\equiv 5\pmod 6$; this condition can be expressed a little more compactly by saying that $N\equiv\pm1\pmod6$. Equivalently, $(N-1)(2N+5)$ is divisible by $6$ if and only if $N$ is divisible by neither $2$ nor $3$: if either $2$ or $3$ divides $N$, then $(N-1)(2N+5)$ is not divisible by $6$.