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.
Best Answer
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}$