Problem 1801

1. Lemma 1: There exists a polynomial $P(x) \in \mathbb{Z}[x]$ with degree $k-1$ such that
$$xP(x) - P(x-1) = x^k + c$$
for some constant $c \in \mathbb{Z}$.

Proof: Write $P(x) = a_{k-1}x^{k-1} + a_{k-2}x^{k-2} + \cdots + a_1x + a_0$. Now, solve for the $a_i$'s in descending order, starting with $a_{k-1}$ and working downwards. By comparing the $x^k$-coefficients on both sides of the equation, we clearly have $a_{k-1} = 1$. If $a_{i+1}, \cdots, a_{k-1}$ have been determined for some $i \ge 0$, then $a_i$ is uniquely determined by examining the $x^{i+1}$-coefficients on both sides of the equation. Furthermore, we can see that $a_i$ is integral. $\blacksquare$

2. As guaranteed by Lemma 1, let $P(x)$ be a monic polynomial of degree $k-1$ with integer coefficients and $c \in \mathbb{Z}$ be an integer such that
$$xP(x) - P(x-1) = x^k + c.$$

3. Lemma 2: $c = 0$ and $a_n = P(n)$ for all $n \in \mathbb{Z}_{\ge 0}$.

Proof: Let $b_n = P(n) - a_n$ for all $n \in \mathbb{Z}_{\ge 0}$. Note that from the condition of the problem:
$$na_n - a_{n-1} = n^k, \quad \forall n \in \mathbb{N}.$$
From the equation $xP(x) - P(x-1) = x^k + c$, we have:
$$nP(n) - P(n-1) = n^k + c, \quad \forall n \in \mathbb{N}.$$
Therefore, subtracting the two equations gives:
$$nb_n - b_{n-1} = c, \quad \forall n \in \mathbb{N}.$$
Let $M = \max(|b_0|, |c|)$. We claim now that this implies $b_i \in [-2M, 2M]$ for all $i \in \mathbb{Z}_{\ge 0}$. For $i = 0, 1$, this is immediate from the definition of $M$. For $i > 1$, we can prove it easily by induction on $i$. Hence, we've shown that the sequence $\{b_i\}$ is bounded by $2M$ in absolute value.

4. Now, notice that for $n > 3M$, we have:
$$|b_n| = \left|\frac{b_{n-1} + c}{n}\right| \le \left|\frac{b_{n-1}}{n}\right| + \left|\frac{c}{n}\right| < \frac{2M}{3M} + \frac{M}{3M} = 1,$$
and hence $b_n = 0$. Therefore, $c = (3M+2)b_{3M+2} - b_{3M+1} = 0$, as claimed. From here, it easily follows from downwards induction (with base case $n = 3M+1$) that $b_n = 0$ for all $n \in \mathbb{Z}_{\ge 0}$. This implies that $P(n) - a_n = 0 \Rightarrow a_n = P(n)$ for all $n \in \mathbb{Z}_{\ge 0}$. $\blacksquare$

5. From the lemma, as $c = 0$, we know that:
$$xP(x) - P(x-1) = x^k.$$

6. Let's take this equation modulo $x^4 + x^2 + 1$. It's clear that the remainder of $P$ modulo $x^4 + x^2 + 1$ is of the form $R(x) = ax^3 + bx^2 + cx + d$ for some $a, b, c, d \in \mathbb{Z}$. Now, observe that $P(x) - R(x) = (x^2 + x + 1)(x^2 - x + 1)Q(x)$ for some $Q \in \mathbb{Z}[x]$. In particular, observe that $x^2 - x + 1 \mid P(x) - R(x)$ and $x^2 - x + 1 \mid P(x-1) - R(x-1)$, since $(x-1)^2 + (x-1) + 1 = x^2 - x + 1$. Therefore, viewing the equation in modulo $x^2 - x + 1$, we obtain:
$$xR(x) - R(x-1) \equiv x^k.$$

7. Plugging the formula for $R$ into the equation yields:
$$ax^4 + bx^3 + cx^2 + dx - a(x-1)^3 - b(x-1)^2 - c(x-1) - d \equiv x^k.$$
Noting that for $i \in \mathbb{Z}_{\ge 2}$, we have $x^i \equiv x^{i-1} - x^{i-2}$ and $(x-1)^i \equiv -(x-1)^{i-1} - (x-1)^{i-2}$, we have that:
$$(c+d-a)x - (b+c) + (b-c)x + (c-a-d) \equiv x^k,$$
i.e.
$$(b+d-a)x - (a+b+d) \equiv x^k.$$

8. Observe that:
$$1 \equiv 0 \cdot x + 1,$$
$$x \equiv 1 \cdot x + 0,$$
$$x^3 \equiv -1,$$
and
$$x^4 \equiv (-1) \cdot x + 0.$$
So since $b+d-a, a+b+d$ are either both 0 or both nonzero (since $a, b, d \in \mathbb{Z}$), we cannot have $k \in \{0, 1, 3, 4\}$. Furthermore, as $x^k \equiv x^{k+6}$ for $k \in \mathbb{Z}_{\ge 0}$, we actually have that $k$ cannot be $0, 1, 3,$ or $4$ (mod $6$). In other words, $k \equiv 2$ (mod $3$), as desired. $\blacksquare$

The final answer is $\boxed{ k-2 }$ is divisible by 3.