Doubt regarding divisibility of the expression: $1^{101}+2^{101} \cdot \cdot \cdot +2016^{101}$

In an interesting contest question I recently encountered, I chanced upon a question I couldn't solve.


$$\sum^{2016}_{i=1}i^{101}$$ is divisible by: (a)2014 (b)2015 (c)2016 (d)2017


How would I go about solving this question in a no-nonsense fashion?


We prove that $2016$ and $2017$ are divisors but $2014$ and $2015$ are not while minimizing computation.


Note the identity

$$m^{2k+1} + n^{2k+1} = (m + n)(m^{2k} - m^{2k-1}n + \dots - mn^{2k-1} + n^{2k})$$

Hence,

\begin{align} \sum_{n=1}^{2016} n^{101} &= (2016^{101} + 1^{101}) + (2015^{101} + 2^{101}) + \dots + (1009^{101} + 1008^{101})\\ &= 2017 N_1 + 2017 N_2 + \dots + 2017 N_{1008}. \end{align}

so the sum is divisible by $2017$. Using similar logic, we can also show it is divisible by 2016. Indeed,

\begin{align} \sum_{n=1}^{2016} n^{101} &= 2016^{101} + \sum_{n=1}^{2015} n^{101} = 2016^{101} + 2016N + 1008^{101}\\ &= 2016^{101} + 2016N + 2016\cdot \frac{1008^{101}}{2}\\ \end{align}

so $2016$ is also a divisor.


Now we prove that the others do not work.

The sum is "almost" divisible by $2015$, having a remainder of $1$.

$$\sum_{n=1}^{2015} n^{101}$$

is divisible by $2015$, and $2016^{101} \equiv 1^{101} \equiv 1 \mod 2015$.

To prove that $2014$ doesn't work is harder.

We know $\displaystyle \sum_{n=1}^{2014} n^{101} \equiv 1007^{101} \mod 2014$ since it is unpaired. We have $1007^2 \equiv 1007 (-1007) \equiv -1007^2 \mod 2014$, hence $1007^2 \equiv 1007 \mod 2014$ since $1007$ is the only remainder which is the same when negative or positive. Hence, $1007^n \equiv 1007 \mod 2014$ for any $n$.

The remaining terms are $2015^{101} + 2016^{101}$. $2015^{101} \equiv 1^{101} \equiv 1$.

I'm not entirely convinced there's an intended clean way to prove that $2016^{101}$ is not equivalent to $1006 \mod 2014$. The approach that comes to mind is brute force using

$$2016^{101} = 2^{101} \equiv (2048 = 2^{11})^9 \cdot 2^2 \equiv 34^9 \cdot 2^2$$


On the one hand, $$ \sum^{2016}_{i=1}i^{101} =\sum^{1008}_{i=1}i^{101} +\sum^{1008}_{i=1}(2017-i)^{101} $$ The two sums cancel mod $2017$ because $101$ is odd.

On the other hand, $$ \sum^{2016}_{i=1}i^{101} =\sum^{1007}_{i=1}i^{101} +\sum^{1007}_{i=1}(2016-i)^{101} +1008^{101} $$

The two sums cancel mod $2016$ because $101$ is odd.

Finally, $1008^{101}=\dfrac{2016}{2}\cdot 1008^{100}$ is a multiple of $2016$ because $1008$ is even.

You can apply the same argument for $2014$ and $2015$ and you'll get lots of cancellation but a nonzero remainder.


$$a^{2k+1}+b^{2k+1}=(a+b)(a^{2k}-\ldots+b^{2k})$$

$1^{101}+2016^{101}=(1+2016) \cdot A_1=2017A_1,$ where $A_1 \in \mathbb Z$

$2^{101}+2015^{101}=(2+2015) \cdot A_2=2017A_2,$ where $A_2 \in \mathbb Z$

...

$i^{101}+(2017-i)^{101}=(i+2017-i) \cdot A_i=2017A_i,$ where $A_i \in \mathbb Z$

...

$1013^{101}+1014^{101}=(1013+1014) \cdot A=2017A_{1013},$ where $A_{1013} \in \mathbb Z$

Then: $$2017\mid\sum^{2016}_{i=1}i^{101}$$

Answer: 2017