Problem 1639

1. **Case 1: $P(0) = 0$**
- If $P(0) = 0$, then $P(x) = xQ(x)$ for some polynomial $Q(x)$ with integer coefficients.
- The sequence $0, P(0), P(P(0)), \ldots$ is $0, 0, 0, \ldots$, which is trivially constant modulo any $n$.
- Therefore, any polynomial of the form $P(x) = xQ(x)$ satisfies the condition.

2. **Case 2: $P(x)$ is a constant polynomial**
- If $P(x) = c$ for some integer $c$, then the sequence $0, P(0), P(P(0)), \ldots$ is $0, c, c, \ldots$, which is eventually constant modulo any $n$.
- Therefore, any constant polynomial satisfies the condition.

3. **Case 3: $P(x)$ is not constant and $P(0) \neq 0$**
- Let $P(x) = \sum_{i=0}^{d} a_i x^i$ where $d = \deg(P) > 0$ and $a_0 = P(0) \neq 0$.
- Define the sequence $x_n$ such that $x_0 = 0$ and $x_{n+1} = P(x_n)$. Then $x_n = P^n(0)$ for all $n$.
- Suppose $p$ is a positive integer such that $p \mid P^i(0)$ for some $i > 1$. Then for all positive integers $k$, we have:
$$P^{ki}(0) \equiv P^{(k-1)i}(0) \equiv \cdots \equiv P^i(0) \equiv 0 \pmod{p}$$
- Taking $n = p$ in the condition, we get that $x_i$ is eventually constant modulo $p$, hence it must be eventually zero modulo $p$.
- Therefore, there exists $N$ such that $p \mid x_i$ for all $i > N$. Hence $p \mid x_i$ and $x_{i+1} = P(x_i) = \sum_{j=0}^{d} a_j x_i^j$ for large $i$.
- Since $p \mid a_j x_i^j$ for all $j > 0$, $p$ must divide $a_0 = P(0)$.
- Thus, if a number divides $P^i(0)$ for some $i$, then $p$ must also divide $P(0)$. So, $P^i(0) \mid P(0) \implies |P^i(0)| = |P(0)|$ for all $i$.

4. **Subcase: $P(P(0)) = P(0)$**
- If $P(P(0)) = P(0)$, then $P(x) = (x - P(0))Q(x) + P(0)$ for some $Q(x) \in \mathbb{Z}[x]$.
- For $x = 0$, we get $Q(0) = 0 \implies Q(x) = xR(x)$ for some $R(x) \in \mathbb{Z}[x]$.
- Therefore, $P(x) = x(x - P(0))R(x) + P(0)$.
- Then $P(P(0)) = P(0)$ and hence inductively $P^i(0) = P^{i+1}(0)$ for all $i > 0$, satisfying the condition.

5. **Subcase: $P(P(0)) = -P(0)$**
- If $P(P(0)) = -P(0)$, we consider two subcases:
- **1st Subcase: $P(P(P(0))) = P(0) = -P(P(0))$**
- By induction, $P^{2i+1}(0) = P^{2i-1}(0) = \cdots = P(0)$ and $P^{2i}(0) = P^{2i-2}(0) = \cdots = P(P(0)) = -P(0)$.
- However, taking $n$ large enough, we have $x_{2i+1} - x_{2i} = 2P(0)$ divisible by $n$, which is a contradiction.
- **2nd Subcase: $P(P(P(0))) = P(P(0)) = -P(0)$**
- Using $P(P(0)) = -P(0)$, there exists $Q(x) \in \mathbb{Z}[x]$ such that $P(x) = (x - P(0))Q(x) - P(0)$.
- For $x = P(P(0))$, we get $P(P(P(0))) = (P(P(0)) - P(0))Q(P(P(0))) - P(0) = 0 \implies Q(P(P(0))) = 0 \implies Q(-P(0)) = 0$.
- Therefore, $Q(x) = (x + P(0))R(x)$ and $P(x) = (x - P(0))(x + P(0))R(x) - P(0)$.
- For $x = 0$, we get $P(0) = -P(0)^2 R(0) - P(0) \implies P(0)R(0) = -2 \implies R(0) = -2/P(0)$.
- Since $P$ has integer coefficients, $P(0)$ must be $\pm 1$ or $\pm 2$.
- Therefore, $P(x) = (x - c)(x + c)(xS(x) - 2/c) - c$ for $c \in \{1, -1, 2, -2\}$ and some $S(x) \in \mathbb{Z}[x]$.

In conclusion, the required polynomials are of the following forms:
- $P(x) = c$
- $P(x) = xQ(x)$
- $P(x) = x(x - c)R(x) + c$
- $P(x) = (x - c)(x + c)(xS(x) - 2/c) - c$ for $c \in \{1, -1, 2, -2\}$, where $Q(x), R(x), S(x)$ are polynomials with integer coefficients.

The final answer is $\boxed{ P(x) = c }$, $P(x) = xQ(x)$, $P(x) = x(x - c)R(x) + c$, and $P(x) = (x - c)(x + c)(xS(x) - 2/c) - c$ for $c \in \{1, -1, 2, -2\}$, where $Q(x), R(x), S(x)$ are polynomials with integer coefficients.