1
$\begingroup$

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)))$, $\ldots$ 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 ?

  • 0
    You might want to take a look at [this](http://math.stackexchange.com/questions/8101/iterated-polynomial-problem).2012-10-28

2 Answers 2

1

Define $a_i = f^i(1)$. So the $a_i$ are just $1,f(1),...$. Now, remark that as $f(n) > n$ we have for some sufficiently large $L$ that $a_{i+1} > 10a_i$ for all $i > 1$ if $\deg f > 1$ (this is simply because $a_i$ is unbounded, and the $10$ is just some big number)

Now, it is well known that for a polynomial $f$ we have $(a-b)|(f(a) - f(b))$ for any integers $a,b$. Now, take some $i > L$. Remark that $f(a_i) - a_i > 9a_i$. However, one can easily show using $(a-b)|(f(a)-f(b))$ that we have $f(a_{k}) \equiv a_k \pmod{f(a_i) - a_i}$ whenever $k \ge i$ via induction. Obviously $(f(a_i) - a_i) \nmid a_i$. Thus we have $(f(a_i) - a_i) \nmid a_k$ for any $k \ge i$. Take $k = f(a_i) - a_i$ to get a desired contradiction, as $k$ does not divide $f(1), ..., f(a_{i-1})$ due to $k > f(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 $f(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.

1

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.