Problem 1929

Let $s_k(n) = 1^k + 2^k + \dots + 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 \pmod{20^{15}}$, or $S(n) \equiv 30a \pmod{30 \times 20^{15} = 3 \times 2^{31} \times 5^{16}}$. Since $S(n)$ is an integer polynomial, $S(n) \equiv a \pmod{m}$ then $S(n+km) \equiv a \pmod{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{align*} S(n) &\equiv 30a \pmod{3} \\ S(n) &\equiv 30a \pmod{2^{31}} \\ S(n) &\equiv 30a \pmod{5^{16}}. \end{align*}$$
For the first equation, it is clear that $S(0) \equiv 30a \pmod{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 \pmod{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 \pmod{2^r}$. We write $n = n_0 + 2^r q$, then
$$S(n) \equiv S(n_0) - 2^r q \pmod{2^{r+1}}.$$
It follows that if we take $q \equiv r \pmod 2$ then $S(n) \equiv 30a \pmod{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$.