About a certain type of polynomial Let $p$ be a polynomial over the set of positive integers such that $p(n) > n$  for all positive integers $n$. It is also known that for every positive positive integer $m$, there exists a term of the sequence $1,\, p(1),\, p(p(1)),\, p(p(p(1))), \dots$ divisible by $m$. Then it is easy to see that $p(n) = n + 1$ satisfies all the criteria, cause then $p(n) > n$ and the sequence becomes $1, 2, 3, \ldots$ just the sequence of all positive integers.
Does there exist any other polynomial which satisfy all the criteria ?
 A: Define $a_i = p^i(1)$. So the $a_i$ are just $1,p(1),...$. Now, remark that as $p(n) > n$ we have for some sufficiently large $L$ that $a_{i+1} > 10a_i$ for all $i > L$ if $\deg f > 1$ (this is simply because $a_i$ is unbounded, and the $10$ is just some big number).
Now, take some $i > L$. Remark that $p(a_i) - a_i > 9a_i$. However, one can easily show using $a-b\mid p(a)-p(b)$ that we have $p(a_{k}) \equiv a_k \bmod{(p(a_i) - a_i)}$ whenever $k \ge i$ by induction. Obviously $(p(a_i) - a_i) \nmid a_i$. Thus we have $(p(a_i) - a_i) \nmid a_k$ for any $k \ge i$. Take $k = p(a_i) - a_i$ to get a desired contradiction, as $k$ does not divide $p(1),..., p(a_{i-1})$ due to $k > p(a_i)$ and the $a_i$ being monotonically increasing.
Thus we are reduced to the degree 1 case, in which Gerry Myerson provides a great proof that $p(n) = n+1$ is the only solution.
BTW, I think this problem is a previous IMO Shortlist Problem or from some country's national olympiad. However, I was unable to determine the source.
A: I don't know. Here's how far I got with the linear case. Suppose $p(x)=ax+b$ with $a,b$ integers, $a\ne1$. Then the $n$th term in your sequence is $$a^n+{a^n-1\over a-1}b$$ For this to be a multiple of some prime $q$, we need $$(a+b-1)a^n\equiv b\pmod q\tag1$$ Now for any $a$, there will be primes $q$ such that $a$ has a relatively small order modulo $q$, and modulo such $q$ there will be very few different values of $a^n$, and very unlikely that any $n$ will satisfy (1). So I'm convinced (although I recognize I haven't given a proof) that there are no such linear polynomials with $a\ne1$. And for $a=1$ it's easy to see $b=1$, since any prime dividing $b$ can't divide any term in the sequence. 
