Putnam 2024, Problem A-2

For which real polynomials \( p \) is there a real polynomial \( q \) such that
\[ p(p(x)) - x = (p(x) - x)^2 q(x) \]
for all real \( x \)?

Solution:
The answer is $p(x) = \pm x + c$ for any $c \in \mathbb{R}$. Note that any such polynomial works: if $p(x) = x + c$ then $p(x) - x = c$, while if $p(x) = -x + c$ then $p(p(x)) - x = 0$. We will show that in fact these are the only polynomials $p(x)$ such that $p(p(x)) - x$ is divisible by $r(x)^2$, where $r(x) = p(x) - x$.

**First solution.** Suppose that $p(p(x)) - x$ is divisible by $r(x)^2$. Then
$$x \equiv p(p(x)) \equiv p(x + r(x)) \equiv p(x) + p'(x)r(x) \pmod{r(x)^2}.$$

In other words, $r(x)(1 + p'(x))$ is divisible by $r(x)^2$. From this, it follows that either $r(x) = 0$ or $1 + p'(x)$ is divisible by $r(x)$. In the first case, we have $p(x) = x$. In the second case, if $1 + p'(x) = 0$ then $p(x) = -x + c$ for some constant $c$; otherwise, we have
$$\deg(p) - 1 = \deg(1 + p'(x)) \geq \deg(r)$$
and this is only possible if $p(x) = x + c$ for some constant $c$.

**Second solution.** Suppose that $p(p(x)) - x$ is divisible by $r(x)^2$. Then
$$0 \equiv \frac{d}{dx}(p(p(x)) - x) = p'(x)p'(p(x)) - 1 \equiv p'(x)^2 - 1 \equiv (p'(x) + 1)(p'(x) - 1) = r'(x)(r'(x) + 2) \pmod{r(x)}.$$

If $\alpha$ is a root of $r(x)$ of some multiplicity $m$, then the multiplicity of $\alpha$ as a root of $r'(x)$ is $m-1$. Consequently, every root of $r(x)$ must be a root of $r'(x) + 2$; in particular such a root cannot also be a root of $r'(x)$, so every root of $r(x)$ is simple. Putting this together, we deduce that $r(x)$ divides $r'(x) + 2$. If $r(x)$ is constant, then $p(x) = x + c$ for some $c$. Otherwise, $\deg(r'(x) + 2) < \deg(r(x))$ and so $r'(x) + 2$ must be zero; then $r(x) = -2x + c$ for some $c$, whence $p(x) = -x + c$.