Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.