Problem 2590

First solution (original one) The proof is split into two essentially orthogonal claims, which we state as lemmas.

**Lemma (Lemma I: elimination of $g$)**
Assume valiant $g: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ exists. Then
$$k! \sum_{x \in \mathbb{Z}/n\mathbb{Z}} x^k \equiv 0 \pmod{n}$$
for $k = 0, 1, \dots, 100$.

Proof. Define $g_x(T) = g(x) + Tx$ for any integer $T$. If we view $g_x(T)^k$ as a polynomial in $\mathbb{Z}[T]$ of degree $k$ with leading coefficient $x^k$, then taking the $k$th finite difference implies that, for any $x$,
$$k! x^k = \binom{k}{0} g_x(k)^k - \binom{k}{1} g_x(k-1)^k + \binom{k}{2} g_x(k-2)^k - \dots + (-1)^k \binom{k}{k} g_x(0)^k.$$
On the other hand, for any $1 \le k \le 100$ we should have
$$\sum_x g_x(0)^k \equiv \sum_x g_x(1)^k \equiv \dots \equiv \sum_x g_x(k)^k \\ \equiv S_k \stackrel{\text{def}}{=} 0^k + \dots + (n-1)^k \pmod{n}$$
by the hypothesis. Thus we find
$$k! \sum_x x^k \equiv \left[ \binom{k}{0} - \binom{k}{1} + \binom{k}{2} - \dots \right] S_k \equiv 0 \pmod{n}$$
for any $1 \le k \le 100$, but also obviously for $k = 0$. $\square$

We now prove the following self-contained lemma.

Lemma (Lemma II: power sum calculation)
Let $p$ be a prime, and let $n, M$ be positive integers such that
$$M \text{ divides } 1^k + 2^k + \dots + n^k$$
for $k = 0, 1, \dots, p-1$. If $p \mid n$ then $\nu_p(M) < \nu_p(n)$.

Proof. The hypothesis means that any polynomial $f(T) \in \mathbb{Z}[T]$ with $\deg f \le p-1$ will have $\sum_{x=1}^n f(x) \equiv 0 \pmod{M}$. In particular, we have
$$\begin{aligned} 0 &\equiv \sum_{x=1}^{n} (x-1)(x-2)\cdots(x-(p-1)) \\ &= (p-1)! \sum_{x=1}^{n} \binom{x-1}{p-1} = (p-1)! \binom{n}{p} \pmod{M}. \end{aligned}$$
But now $\nu_p(M) \le \nu_p\left(\binom{n}{p}\right) = \nu_p(n) - 1$. $\square$

Now assume for contradiction that valiant $g: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ exists, and $p \le 101$ is the smallest prime dividing $n$. Lemma I implies that $k! \sum_x x^k \equiv 0 \pmod{n}$ for $k = 1, \dots, p-1$ and hence $\sum_x x^k \equiv 0 \pmod{n}$ too. Thus $M=n$ holds in the previous lemma, impossible.

A second solution Both lemmas above admit variations where we focus on working modulo $p^e$ rather than working modulo $n$.

Lemma (Lemma I')
Assume valiant $g: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ exists. Let $p \le 101$ be a prime, and $e = \nu_p(n)$. Then
$$\sum_{x \in \mathbb{Z}/n\mathbb{Z}} x^k \equiv 0 \pmod{p^e}$$
for $k = 0, 1, \dots, p-1$.

Proof. This is weaker than Lemma I, but we give an independent specialized proof. Begin by writing
$$\sum_x (g(x) + Tx)^k \equiv \sum_x x^k \pmod{p^e}.$$
Both sides are integer polynomials in $T$, which vanish at $T = 0, 1, \dots, p-1$ by hypothesis (since $p-1 \le 100$).
We now prove the following more general fact: if $f(T) \in \mathbb{Z}[T]$ is an integer polynomial with $\deg f \le p-1$, such that $f(0) \equiv \dots \equiv f(p-1) \equiv 0 \pmod{p^e}$, then all coefficients of $f$ are divisible by $p^e$. The proof is by induction on $e \ge 1$. When $e=1$, this is just the assertion that the polynomial has at most $\deg f$ roots modulo $p$. When $e \ge 2$, we note that the previous result implies all coefficients are divisible by $p$, and then we divide all coefficients by $p$.
Applied here, we have that all coefficients of
$$f(T) \stackrel{\text{def}}{=} \sum_x (g(x) + Tx)^k - \sum_x x^k$$
are divisible by $p^e$. The leading $T^k$ coefficient is $\sum_k x^k$ as desired. $\square$

Lemma (Lemma II')
If $e \ge 1$ is an integer, and $p$ is a prime, then
$$\nu_p (1^{p-1} + 2^{p-1} + \dots + (p^e - 1)^{p-1}) = e - 1.$$
Proof. First, note that the cases where $p=2$ or $e=1$ are easy; since if $p=2$ we have $\sum_{x=0}^{2^e-1} x \equiv 2^{e-1}(2^e-1) \equiv -2^{e-1} \pmod{2^e}$, while if $e=1$ we have $1^{p-1} + \dots + (p-1)^{p-1} \equiv -1 \pmod{p}$. Henceforth assume that $p > 2, e > 1$.
Let $g$ be an integer which is a primitive root modulo $p^e$. Then, we can sum the terms which are relatively prime to $p$ as
$$S_0 \stackrel{\text{def}}{=} \sum_{\text{gcd}(x,p)=1} x^{p-1} \equiv \sum_{i=1}^{\varphi(p^e)} g^{(p-1)\cdot i} \equiv \frac{g^{p^{e-1}(p-1)^2} - 1}{g^{p-1} - 1} \pmod{p^e}$$
which implies $\nu_p(S_0) = e-1$, by lifting the exponent. More generally, for $r \ge 1$ we may set
$$S_r \stackrel{\text{def}}{=} \sum_{\nu_p(x)=r} x^{p-1} \equiv (p^r)^{p-1} \sum_{i=1}^{\varphi(p^{e-r})} g_r^{(p-1)\cdot i} \pmod{p^e}$$
where $g_r$ is a primitive root modulo $p^{e-r}$. Repeating the exponent-lifting calculation shows that $\nu_p(S_r) = r(p-1) + ((e-r)-1) > e$, as needed. $\square$

Assume to the contrary that $p \le 101$ is a prime dividing $n$ and a valiant $g: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ exists. Take $k = p-1$ in Lemma I' to contradict Lemma II'

A third remixed solution We use Lemma I and Lemma II' from before. As before, assume $g: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ is valiant, and $n$ has a prime divisor $p \le 101$. Also, let $e = \nu_p(n)$.
Then $(p-1)! \sum_{x} x^{p-1} \equiv 0 \pmod{n}$ by Lemma I, and now
$$\begin{aligned} 0 &\equiv \sum_{x} x^{p-1} \pmod{p^e} \\ &\equiv \frac{n}{p^e} \sum_{x=1}^{p^e-1} x^{p-1} \not\equiv 0 \pmod{p^e} \end{aligned}$$
by Lemma II', contradiction.

A fourth remixed solution We also can combine Lemma I' and Lemma II. As before, assume $g: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ is valiant, and let $p$ be the smallest prime divisor of $n$.
Assume for contradiction $p \le 101$. By Lemma I' we have
$$\sum_{x} x^k \equiv 0 \pmod{p^e}$$
for $k=0, \dots, p-1$. This directly contradicts Lemma II with $M = p^e$.