Number system, divisibility For how many values of $n$, where $n<55$, is the expression $(n)(n+1)(2n+1)/6$ divisible by $4$? I checked $n$ and $n+1$ separately for divisibility by $4$. My ans came out to be $26$. But the answer is $12$. Why?
 A: $$ 
\frac16 n(n+1)(2n+1) \bmod 4 =0
$$
if $n=8k$ of $n=8k+7$. Using Aleksander's hint: $\sum\limits_{i = 1}^ni^2 = \frac{n(n+1)(2n+1)}{6}$ you can easily check that if you sum up the first eight values, you get $4$ odd and $4$ even values, which makes the overall sum divisble by $4$. The last value is $8^2$, so you may even skip the $8^{\text{th}}$ value. This pattern repeats again after eight more values.
You can check this by substituting $n \to 8k$ to get: $\frac43 n (8 n+1) (16 n+1)$. $n\to 8k+7$ is left as an exercise...
And you have six values $8k$ and six values $8k+7$ (including $k=0$) below $55$, which makes $12$ in total.
A: Can you see that it's the same as asking for $n(n+1)/2$ to be divisible by 4? And can you see how to solve that problem?
A: Hint $\ $ Specialize $\, g(x) = 2x+1\,$ below.
Theorem $\ $ Let $\,g(x)\,$ be a polynomial with integer coeffcients such that $\,\color{#c00}{2\nmid g(n)}\,$ for integers $\,n.$
Then $\ 3\mid g(1)\,\Rightarrow\, 6\mid f(n) = n(n\!+\!1)g(n).\ $ If so, then $\ 4\mid f(n)/6 \iff n\equiv -1,0\pmod 8$
Proof $ $ (sketch) $\ f(n)\,$ has roots $\,n\equiv 0,-1\,$ mod $\,2,3,$ and, further, has root $\,n\equiv 1\pmod 3,\,$ by $\,3\mid g(1).\,$ Therefore $\,2,\color{#0a0}{3\mid f(n)}\,\Rightarrow\, 6\mid f(n).\,$ The second claim follows from
$4\mid f(n)/6\iff 3\cdot 8\mid f(n)\iff 3,8\mid f(n)\overset{\large\color{#c00}{2\,\nmid\ g(n)}}{\large \underset{\color{#0a0}{ 3\,\mid\, f(n)}}\iff} 8\mid n(n\!+\!1)\iff 8\mid n\ $ or $\ 8\mid n\!+\!1\,\  $ QED
