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

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 ?

share|cite|improve this question
You might want to take a look at this‌​. – EuYu Oct 28 '12 at 5:56
up vote 1 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.