Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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