Problem 5

Let

P(x)

be a polynomial of degree

n>1

with integer coefficients, and let

k

be a positive integer. Define

Q(x)=P(P(\ldots P(x)\ldots))

, where

P

occurs

k

times. Prove that there are at most

n

integers

t

such that

Q(t)=t

Step 1 of 8: Record the integer divisibility lemma

Previous step Next step

u-v\mid P(u)-P(v)\qquad(u,v\in\mathbb Z,\ u\ne v)

Detailed analysis

For distinct integers $u,v$ , every term $u^j-v^j$ is divisible by $u-v$ . Since $P$ has integer coefficients, summing these divisibilities gives $u-v\mid P(u)-P(v)$ .