Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
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
up vote 3 down vote accepted

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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.