# Iterated polynomial problem

Polynomial $P$ satisfies $P(n)>n$ for all positive integers $n$. Every positive integer $m$ is a factor of some number of the form $P(1),P(P(1)),P(P(P(1))),\ldots$. Prove that $P(x)=x+1$.

-
The polynomial $P(x) = x+2$ is also a valid solution isn't it? I think any polynomial of the form $P(x) = x +k$ where $k$ is an integer would be a valid polynomial. – svenkatr Oct 27 '10 at 21:01
@svenkat: No, in that case all the P(P(...P(1)...)) are odd. – Aryabhata Oct 27 '10 at 21:10
What is the source of this problem? Do you know it, Jaska? – Aryabhata Oct 27 '10 at 21:10
@Jaska: are the coefficients of the polynomial assumed to be integers? – Yuval Filmus Oct 27 '10 at 21:11
I think the spirit of the problem requires integer coefficients. Otherwise $P(x)=x+\frac{1}{2}$ works as well – Ross Millikan Oct 28 '10 at 0:06

Denote the iterates by $x_0 = 1, x_{n+1} = P(x_n)$.

Assume that the coefficients of $P$ are integral.

If at some point $P(x_n) > 2x_n$, then I claim that $m = P(x_n)-x_n$ does not divide any iterate. First, $x_n < m$, so $x_0,\ldots,x_n$ cannot be divisible by $m$. Second, we prove by induction that for $k \geq n$, $x_k \equiv x_n \pmod{m}$:

$x_{k+1} = P(x_k) \equiv P(x_n) \equiv x_n \pmod{m}$.

Since $x_n < m$, we see that $m$ doesn't divide any of the iterates.

We conclude that always $P(x_n) \leq 2x_n$. Thus $P(x) = ax+b$ with $a \leq 2$. On the one hand $P(1) > 1$, and on the other hand $P(1) \leq 2$. Thus $P(1) = 2$, and therefore either $a = 1$ or $a = 2$. If $a = 2$ then $P(x) = 2x$, and we generate only powers of $2$. Thus $a = 1$ and $P(x) = x + 1$.

-
I don't see how you get $x_k \equiv x_n \pmod{m}$. It's true for n+1, but why should $P(x_{n+2}) \equiv P(x_{n+1}) \pmod{m}$? – Ross Millikan Oct 27 '10 at 23:53
@Ross $P(x_k) - P(x_n)$ is divisible by $x_k - x_n$. – Yuval Filmus Oct 27 '10 at 23:59
I thought it was by induction, but didn't see why $P(x_{n+2})-x_{n+2} \equiv P(x_{n+1})-x_{n+1} \pmod m$ – Ross Millikan Oct 28 '10 at 0:04