Powers Get Huge Really Fast

Let $Z$ denote the value of the sum, $1^{2016} + 2^{2016} +\cdots + 2016^{2016}$ . So we want to find the remainder of when $Z$ is divided by 2016.

Since 2016 is not a prime number, let's start breaking 2016 into product of pairwise coprime positive integers to get $2016 = 32 \times 7 \times 9$ .

This suggests that we want to find $Z$ modulo $32, 7$ and $9$ separately so that we can apply chinese remainder theorem .

Let us start by finding $Z \bmod{32}$ , and we partition the terms of $Z$ as such

$\begin{aligned} 1^{2016} + 2^{2016} +\cdots + 2016^{2016} &=& \left( 1^{2016} + 2^{2016} + \cdots + 32^{2016} \right) \\ && + \left( 33^{2016} + 34^{2016} + \cdots + 64^{2016} \right) \\ && + \left( 65^{2016} + 36^{2016} + \cdots + 96^{2016} \right) \\ && + \cdots \\ && + \left( 1985^{2016} + 1986^{2016} + \cdots + 2016^{2016} \right) \end{aligned}$

Taking modulo 32, we have

$\begin{aligned} && 1^{2016} + 2^{2016} +\cdots + 2016^{2016} \\ &\equiv& \left( 1^{2016} + 2^{2016} + \cdots + 31^{2016} \right) \\ && + \left( 1^{2016} + 2^{2016} + \cdots + 31^{2016} \right) \\ && + \left( 1^{2016} + 2^{2016} + \cdots + 31^{2016} \right) \\ && + \cdots \\ && + \left( 1^{2016} + 2^{2016} + \cdots + 31^{2016} \right) \\ &\equiv& \dfrac{2016}{32} \times \left( 1^{2016} + 2^{2016} + \cdots + 31^{2016} \right) \\ &\equiv& 63 \left( 1^{2016} + 3^{2016} + 5^{2016} + \cdots + 29^{2016} + 31^{2016} \right) , \quad \text{ all the even powers are divisible by 32} \\ &\equiv& 63 \left( 1^{2016 \bmod{\phi(32)}} + 3^{2016\bmod{\phi(32)}} + 5^{2016\bmod{\phi(32)}} + \cdots + 31^{2016\bmod{\phi(32)}} \right), \quad \text{ by Euler totient function} \\ &\equiv& 63 \left( 1 \times 16 \right) \equiv 16 \\ \end{aligned}$

Thus we have $Z \bmod {32} = 16$ .

Analogously, let us find $Z \bmod 7$ and $Z \bmod 9$ .

For $Z\bmod 7$ , partitioning the terms gives

$\begin{aligned} &&1^{2016} + 2^{2016} +\cdots + 2016^{2016} \\ &=& \left( 1^{2016} + 2^{2016} + \cdots + 7^{2016} \right) \\ && + \left( 8^{2016} + 9^{2016} + \cdots + 14^{2016} \right) \\ && + \left( 15^{2016} + 16^{2016} + \cdots + 21^{2016} \right) \\ && + \cdots \\ && + \left( 2010^{2016} + 1986^{2016} + \cdots + 2016^{2016} \right) \\ &\equiv & \left( 1^{2016} + 2^{2016} + \cdots + 7^{2016} \right) \\ && + \left( 1^{2016} + 2^{2016} + \cdots + 7^{2016} \right) \\ && + \left( 1^{2016} + 2^{2016} + \cdots + 7^{2016} \right) \\ && + \cdots \\ && + \left( 1^{2016} + 1986^{2016} + \cdots + 7^{2016} \right) \\ &\equiv & \dfrac{2016}7 \left( 1^{2016} + 2^{2016} + \cdots + 6^{2016} \right) \\ &\equiv & 288 \left( 1^{2016} + 2^{2016} + \cdots + 6^{2016} \right) \\ &\equiv & 288 \left( 1^{2016 \bmod{\phi(7)}} + 2^{2016 \bmod{\phi(7)}} + \cdots + 6^{2016 \bmod{\phi(7)}} \right) \\ &\equiv & 288 \left( 1 \times 6 \right) \equiv 6 \\ \end{aligned}$

Lastly, to find $Z \bmod 9$ , partitioning the terms gives us

$\begin{aligned} &&1^{2016} + 2^{2016} +\cdots + 2016^{2016} \\ &=& \left( 1^{2016} + 2^{2016} + \cdots + 9^{2016} \right) \\ && + \left( 10^{2016} + 11^{2016} + \cdots + 18^{2016} \right) \\ && + \left( 19^{2016} + 20^{2016} + \cdots + 27^{2016} \right) \\ && + \cdots \\ && + \left( 2008^{2016} + 1986^{2016} + \cdots + 2016^{2016} \right) \\ &\equiv & \left( 1^{2016} + 2^{2016} + \cdots + 9^{2016} \right) \\ && + \left( 1^{2016} + 2^{2016} + \cdots +9^{2016} \right) \\ && + \left( 1^{2016} + 2^{2016} + \cdots + 9^{2016} \right) \\ && + \cdots \\ && + \left( 1^{2016} + 1986^{2016} + \cdots + 9^{2016} \right) \\ &\equiv & \dfrac{2016}9 \left( 1^{2016} + 2^{2016} + \cdots + 8^{2016} \right) \\ &\equiv & 224 \left( 1^{2016} + 2^{2016} + \cdots + 8^{2016} \right) \\ &\equiv & 224 \left( 1^{2016 \bmod{\phi(9)}} + 2^{2016 \bmod{\phi(9)}} + 4^{2016 \bmod{\phi(9)}} + 5^{2016 \bmod{\phi(9)}} + 7^{2016 \bmod{\phi(9)}} + 8^{2016 \bmod{\phi(9)}} \right) \\ &\equiv & 224 \times 6 \equiv 3 \end{aligned}$

Writing these three linear congruences together, we have $Z \bmod {32} = 16, Z \bmod7 = 6, Z \bmod 9 = 3$ , or equivalently we want to find the smallest positive integer $x$ satisfying the following linear congruences:

$\begin{aligned} x &\equiv& 16 \pmod{32} \\ x &\equiv& 6 \pmod{7} \\ x &\equiv& 3 \pmod{9} \end{aligned}$

We can of course solve these linear congruences systematically by Chinese Remainder Theorem, but that isn't necessary because it's slightly tedious, notice that from these congruences, we have

$\begin{aligned} x &\equiv& 16, 48, 80, 112, 144, \ldots \\ x &\equiv& 6, 13, 20, 27, 34, 41, 48, \ldots \\ x &\equiv& 3, 12, 21, 30, 39, 48, \ldots \end{aligned}$

And the smallest integer that appears in all these three rows is 48. Thus the smallest positive integer $x$ is 48, and so the answer to this question is $\boxed{48}$ as well.

---

Footnote : We can only apply euler's totient function for coprime $a,n$ such that $a^{m} \bmod n = a^{m \, \bmod{\phi (n)}} \bmod n$ can be true.