What is the remainder when $1^{2016} + 2^{2016} + ⋯ + 2016^{2016}$ is divided by $2016$?
My Approach:
started breaking 2016 into product of pairwise coprime positive integers to get $2016 = 32 * 7 * 9$ This suggests that we want to find the sum modulo 32,7, 9 separately so that we can apply the chinese remainder theorem.
but I couldn't solve it any further than this so please help me out.
On
$$S_7=\sum_{r=0}^{287}\left((7r+1)^{2016}+(7r+2)^{2016}+(7r+3)^{2016}+(7r+4^{2016}+(7r+5)^{2016}+(7r+6)^{2016}\right)$$
As $2016\equiv0\pmod6,a^{2016}\equiv1\pmod7$ if $(a,7)=1$
$$S_7\equiv288\equiv\sum_{r=0}^{287}(1+1+1+1+1+1+0)\equiv1(-1)\text{ as }288\equiv1\ \ \ \ (1)$$
Again using Carmichael Function $\lambda(32)=2^{32/4}$,
$$S_{32}=\sum_{r=1}^{2016/2}(2r)^{2016}+\sum_{r=1}^{2016/2}(2r-1)^{2016}\equiv\sum_{r=1}^{2016/2}0+\sum_{r=1}^{2016/2}1\pmod{32}\equiv1008\equiv?\ \ \ \ (2)$$
Finally,
$$S_9=\sum_{r=1}^{2016/3}(3r)^{2016}+\sum_{r=1}^{2016/3}((3r-2)^{2016}+(3r-1)^{2016})$$ $$\equiv\sum_{r=1}^{2016/3}0++\sum_{r=1}^{2016/3}(1+1)\equiv?\ \ \ \ (3)$$
Now apply Chinese remainder theorem on $(1),(2),(3)$
Define $$S = \sum_{i=1}^{2016} i^{2016}$$
Notice that $2016 = 32\cdot 9\cdot7$
and $\phi(32) | 2016,\; \phi(9) |2016,\; \phi(7) | 2016$, so we have
$$i^{2016} \equiv \begin{cases} 1 \pmod n \text{ if } \gcd(i,n)=1\\ 0 \pmod n \text{ if } \gcd(i,n)>1 \end{cases}$$ for $n=32,9,7$.
Then each group of $n$ has $\phi(n)$ values coprime to $n$ and there are $2016/n$ such groups in each case so: $$S \equiv \frac{2016}{32}\cdot \phi(32) \equiv 7\cdot 9 \cdot \phi(32) \pmod{32} \tag 1$$ $$S \equiv \frac{2016}{9}\cdot \phi(9) \equiv 32\cdot 7 \cdot \phi(9) \pmod{9} \tag 2$$ $$S \equiv \frac{2016}{7}\cdot \phi(7) \equiv 9 \cdot 32 \cdot \phi(7) \pmod{7} \tag 3$$
Can you end it now?
Update:
There's a shortcut to CRT. Simply add RHS of $(1), (2), (3)$,
$$x = 7 \cdot 9 \cdot \phi(32) + 32 \cdot 7 \cdot \phi(9) + 9 \cdot 32 \cdot \phi(7) = 4080$$
Then $S \equiv x \pmod{32,9,7} \implies S\equiv x = 4080 \equiv 48 \pmod{2016}$