IMO 2015 Team Selection Tests

Let $s_k(n)=1^k+2^k+\cdots +n^k$. We rewrite the property $T(m)$ as follows: a positive integer $k$ has the property $T(m)$ if $s_k(n)$ covers the complete residue system modulo $m$ when $n$ is a positive integer.

a. We note that if $k>1$ has the property $T(20)$ then so does $k+4$. This fact follows from the property that $n^{k+4}-n^k$ is divisible by $20$ for all $n$, $k>1$. So, we only need to check the property $T(20)$ for $k=1,2,3,4,5$. By direct computation, we have $k=4$ has the property $T(20)$ while $k=1,2,3,5$ do not. Therefore, the positive integer $k$ has the property $T(20)$ if and only if $k$ is divisible by $4$.

b. From part a), $k=1,2,3$ do not have the property $T(20^{15})$. We will show that $k=4$ has the property $T(20^{15})$. It suffices to show that $s_4(n)$ covers the complete residue system modulo $20^{15}$ when $n$ is a positive integer. Let $S(n)=30s_4(n)$, we only need to show that for any integer $a$, there exists an integer $n$ such that $s_4(n)\equiv a(\mathrm{mod}20^{15})$, or $S(n)\equiv 30a(\mathrm{mod}30\times 20^{15}=3\times 2^{31}\times 5^{16})$. Since $S(n)$ is an integer polynomial, $S(n)\equiv a(\mathrm{mod}m)$ then $S(n+km)\equiv a(\mathrm{mod}m)$ for all integer $k$. It follows from the Chinese Remainder Theorem, we only need to show that for any $a$, each of the following congruent equations has a solution $$\begin{array}{rl}S(n)& \equiv 30a(\mathrm{mod}3)\\ S(n)& \equiv 30a(\mathrm{mod}{2}^{31})\\ S(n)& \equiv 30a(\mathrm{mod}{5}^{16}).\end{array}$$ For the first equation, it is clear that $S(0)\equiv 30a(\mathrm{mod}3)$.

Now we show that the second equation has a solution for any $a$. We will prove by induction on $r$ that for any $r$, the equation $S(n)\equiv 30a(\mathrm{mod}{2}^r)$ is solvable. When $r=1$, one can take $n=0$. Suppose that the statement holds for $r$, that is, there exists $n_0$ such that $S(n_0)\equiv 30a(\mathrm{mod}{2}^r)$. We write $n=n_0+2^{r}q$, then $$S(n)\equiv S(n_0)-2^{r}q(\mathrm{mod}{2}^{r+1}).$$ It follows that if we take $q\equiv r(\mathrm{mod}2)$ then $S(n)\equiv 30a(\mathrm{mod}{2}^{r+1})$. Hence, the statement holds for $r+1$. By the induction principle, the statement holds for all $r$. In other words, the second equation has an integer solution for any $a$.

The solvability of the third equation can be done similarly. Therefore, the minimum value of $k$ having the property $T(20^{15})$ is $k=4$.