If $x_1^3+x_2^3+\ldots+x_t^3=2002^{2002}$, find minimum value of $t$ so the condition can be satisfied by some natural numbers $x_i$ If $x_1^3+x_2^3+\ldots+x_t^3=2002^{2002}$, find the minimum value of $t$ so the condition can be satisfied by some natural numbers $x_i$.  
My attempt:
I took modulo $9$ on both sides and found the answer, but my question is why should I take modulo $9$? Why not any other number? What would be your way of solving the problem?
 A: You want to take a modulus $m$ such that $x^3$ takes few values modulo $m$ (thereby reducing the number of possibilities). Since $x^{\phi(m)} \equiv 1 \mod m$ when $x$ is relatively prime to $m$, it would be nice if $3 \mid \phi(m)$. Since $\phi(m)$ is always even, this means $6 \mid \phi(m)$ and $6 \leq \phi(m)$. The first choices for $m$ for which this is true are $m=7$ and $m=9$, so these are the obvious choices. In fact, for both $m=7$ and $m=9$ we have $x^3 \equiv 0, \pm 1 \mod m$.
A: You see easily that (3k)^3 = 0 (modulo 9), (3k+1)^3 = 1 (modulo 9), and (3k-1)^3 = -1 (modulo 9). If you want to write a number of the form 4 (modulo 9) as the sum of cubes, then you need at least four cubes of the form 1 (modulo 9) or five of the form -1 (modulo 9), so you really need at least 4 cubes. Doing it in my head, I think 2002^2002 is actually 4 (modulo 9), so four cubes are needed. 
This doesn't prove that four cubes are enough, but heuristically it is most likely true because of the enormous number of possible sums of four cubes, but actually finding a solution will be impossible (unless you are about ten times better at maths than I am). 
