Evaluate this without a calculator

Question

Evaluate $$1^{2017}+2^{2017}+...+1000^{2017}(\text{mod}\; 2016)$$ These large exponents prevent me from finding any quick method to find the mod.

Answer 1

$2016 = 2^5 \cdot 3^2 \cdot 7$, so do it mod $2^5$, $3^2$ and $7$ and use Chinese Remainder Theorem.

For $2^5 = 32$, note that $\phi(2^5) = 16$, and $2017 \equiv 1 \mod 16$ so $a^{2017} \equiv a \mod 2^5$ if $a$ is odd, while $a^{2017} \equiv 0 \mod 2^5$ if $a$ is even. Thus $1^{2017} + 2^{2017} + \ldots 1000^{2017} \equiv 1 + 3 + \ldots + 999 = 250000 \equiv 16 \mod 2^5$.

I'll leave the rest to you.