We use the fact that $m-n\mid P(m)-P(n)$. For $n$ large enough, the sequence $x_n$ becomes strictly increasing. Given $n$ large enough, there exists $m>n$ s.t. $x_n-x_{n-1}\mid x_m\Rightarrow x_n-x_{n-1}\mid x_{m-1}\Rightarrow \cdots\Rightarrow x_n-x_{n-1}\mid x_n\Rightarrow x_n-x_{n-1}\mid x_{n-1}$, so $x_n\le 2x_{n-1}$, so there are infinitely many $n$ for which $P(n)\le 2n$, so $P$ has degree $1\Rightarrow P(x)=ax+b$. By an argument similar to this one, it's easy to show that $P(1)=2$, so $a+b=2$. We use this argument one more time to find that $P(2)-2\mid 2$, so $P(2)\in \{3,4\}$, so $2a+b\in \{3,4\}$. This means that $P(x)=ax+b\in \{x+1,2x\}$. From now on it's easy. Is it Ok?

That problem appeared in M&Y Magazine (Vietnam) ,for junior students.

grobber wrote: We use the fact that $m-n|P(m)-P(n)$. For $n$ large enough, the sequence $x_n$ becomes strictly increasing. Given $n$ large enough, there exists $m>n$ s.t. $x_n-x_{n-1}|x_m\Rightarrow x_n-x_{n-1}|x_{m-1}\Rightarrow \cdots\Rightarrow x_n-x_{n-1}|x_n\Rightarrow x_n-x_{n-1}|x_{n-1}\Rightarrow \nolinebreak x_n\le \nolinebreak 2x_{n-1}$, so there are infinitely many $n$ for which $P(n)\le 2n$, so $P$ has degree $1\Rightarrow P(x)=ax+b$. By an argument similr to this one, it's easy to show tht $P(1)=2$, so $a+b=2$. We use this rgument one more time to find that $P(2)-2|2$, so $P(2)\in \{3,4\}$, so $2a+b\in \{3,4\}$. This means that $P(x)=ax+b\in \{x+1,2x\}$. From now on it's easy. Is it Ok? After almost 10 years,I fear that your solution is wrong.How can how get that the first line implies the second line implies ...... ??

@ sayantanchakraborty , I suppose you mean $x_{n+1}-x_n |x_m \Rightarrow x_{n+1}-x_n|x_{m-1}\Rightarrow .... $ Because of the property for all $N$ there exists $x_i$ divisible by $N$ , then there exists $m$ such that $x_{n+1}-x_n|x_m$ . Using $a-b|P(a)-P(b)$ , we get $x_{n+1}-x_n|x_m-x_{m-1}$ for all $m>n$ . Combining them together we get $x_{n+1}-x_n|x_m$ if $m\geq n$ .

grobber wrote: We use the fact that $m-n\mid P(m)-P(n)$. For $n$ large enough, the sequence $x_n$ becomes strictly increasing. Given $n$ large enough, there exists $m>n$ s.t. $x_n-x_{n-1}\mid x_m\Rightarrow x_n-x_{n-1}\mid x_{m-1}\Rightarrow \cdots\Rightarrow x_n-x_{n-1}\mid x_n\Rightarrow x_n-x_{n-1}\mid x_{n-1}$, so $x_n\le 2x_{n-1}$, so there are infinitely many $n$ for which $P(n)\le 2n$, so $P$ has degree $1\Rightarrow P(x)=ax+b$. By an argument similar to this one, it's easy to show that $P(1)=2$, so $a+b=2$. We use this argument one more time to find that $P(2)-2\mid 2$, so $P(2)\in \{3,4\}$, so $2a+b\in \{3,4\}$. This means that $P(x)=ax+b\in \{x+1,2x\}$. From now on it's easy. Is it Ok? For $n$ large enough, the sequence $x_n$ becomes strictly increasing. Given $n$ large enough, there exists $m>n$ s.t. $x_n-x_{n-1}|x_m$ Why Why?? I can explain as follows: $\mathop {\lim }\limits_{x \to + \infty } ( {P( {x} ) - 2x = + \infty \Rightarrow }$ For $n$ large enough, we have $P( {{x_{n - 1}}} ) - P( {{x_{n - 2}}} ) > P( {{x_{n - 2}}} ) \Leftrightarrow {x_n} - {x_{n - 1}} > {x_{n - 1}}$. So hypothetically exist $m$ s.t: ${x_n} - {x_{n - 1}}|{x_m} \Rightarrow {x_m} \ge {x_n} - {x_{n - 1}} > {x_{n - 1}} \Rightarrow m \ge n$ $ \Rightarrow {x_n} - {x_{n - 1}}|{x_m} - {x_{m - 1}} \Rightarrow {x_n} - {x_{n - 1}}|{x_{m - 1}}$ and continue as above solution.

Obviously the sequence ain't bounded as that would brake the divisibility by taking a sufficiently large number.Supposes $\deg P\geq 2$.This would imply that after a certain point $P(x)>2x$ for all $x>M$.Now notice by Bezout's we have :$x_i-x_{i-1}|x_{i+1}-x_i$ and hence by choosing $m:=x_i-x_{i-1}$ the sequence $x_i$ in $\mathbb{Z}_{m}$ is onwardly constant .Notice that $x_i-x_{i-1}>x_{i-1}$ for a large $i$ but $x_i-x_{i-1}\mid x_{i-1}$ or less a contradiction.Hence $P$ is linear.If it's monic simply take $m$ to be its free term.Else $x_i=a^{n}+b\frac{a^n-1}{a-1}$ now by taking $m:=a$ we have $a\mid b$ and hence by scalling down the whole sequence by $a$ we obtain a monic linear poly,impossible.$\blacksquare$

Omid Hatami wrote: $p$ is a polynomial with integer coefficients and for every natural $n$ we have $p(n)>n$. $x_k $ is a sequence that: $x_1=1, x_{i+1}=p(x_i)$ for every $N$ one of $x_i$ is divisible by $N.$ Prove that $p(x)=x+1$

anantmudgal09 wrote: Omid Hatami wrote: $p$ is a polynomial with integer coefficients and for every natural $n$ we have $p(n)>n$. $x_k $ is a sequence that: $x_1=1, x_{i+1}=p(x_i)$ for every $N$ one of $x_i$ is divisible by $N.$ Prove that $p(x)=x+1$

What does $\text{def}$ mean ?

@above $\text{def}$ just stands for definition. Basically, it means we are just defining something right now and it wasn't defined before (so that the reader doesn't waste time thinking was this defined before or not). We show by induction on $m \ge 1$ that $x_i = i ~ \forall ~ 1 \le i \le m$. Base case $x_1 = 1$ is given. Assume assertion is true for $m = k-1$ (with $k \ge 2$), i.e. $x_i = i ~ \forall ~ 1 \le i \le k-1$. Now $x_1 < x_2 < \cdots$. So $x_k := C > x_{k-1} = k-1$. If $C > k$, then modulo $C-1$ the sequence is just $$ 1,2,\ldots,k-1 ; 1,2,\ldots,k-1 ; \ldots $$so no number is divisible by $C-1$, contradiction. Hence $C = k$, completing the induction step. $\blacksquare$

Observe that $1 \equiv P(1) \equiv P^2(1) \equiv ... \pmod{P(1)-1}$, so from the problem condition, we have that there exists an $N$ such that $P(1)-1|P^N(1)$, so $P(1)-1|1$, thus $P(1)-1=1$, since $P(1)>1$. Thus, $P(1)=2$. Now, assume by induction that $P(k)=k+1$ for all $k=1,2,...,n$. Therefore, $P(1)=2,P^2(1)=P(2)=3,...,P^n(1)=P(n)=n+1$. Observe that the chain $1 \mapsto P(1) \mapsto P^2(1) \mapsto ...$ is equals to $1 \mapsto 2 \mapsto 3 \mapsto ... \mapsto n \mapsto n+1 \mapsto 1 \pmod{P^{n+1}(1)-1=P(n+1)-1}$. From the problem condition, there is exists an $N$ such that $P^{n+1}(1)-1=P(n+1)-1|P^N(1)$, and $P^N(1)$ belongs to $1,2,...,n+1 \pmod{P(n+1)-1}$. Hence, $P(n+1)-1|k$ for some $1 \leq k \leq n+1 \implies n< P(n+1)-1 \leq k \leq n+1 \implies P(n+1)-1=n+1 \implies P(n+1)=n+2$, for all $n \in \mathbb{Z}_{\geq 0}$. This implies that $P(X) \equiv X+1$, as desired. $\blacksquare$

Nice problem. Take some positive integer $n$ and plugging $N=x_n-x_{n-1}$ gives that there exists $i>n$ such that $x_n-x_{n-1} \mid x_i$ and since $x_n-x_{n-1} \mid x_i-x_{i-1}$, we get that $x_n-x_{n-1} \mid x_{i-1}$ and so on until we get that $x_n-x_{n-1} \mid x_{n-1}$ , hence $x_n \leq 2x_{n-1}$ (if $i<n$, since it is given that the sequence is increasing, $x_i \leq x_{n-1}$ and we directly obtain the above mentioned result). Since this holds for all large $n$, we get that the polynomial $P$ grows too slowly ($P(x) \leq 2x$ holds for infinitely many $x$), hence it is linear. If $P(x)=ax+b$, then $P^k(1)=x_k=a^{k}+b\frac{a^k-1}{a-1}$ and let WLOG $(a,b)=1$ (otherwise divide everything by the $gcd$). If $a=1$, then $P^k(1)=kb+1$, so plug $N=b$ to see there are no multiples of $b$. Otherwise, plug $N=a$ to see $a \mid b$, contradiction with the $gcd$ assumption.

Let $P(n) = p(n)$. We have $(x_i) = \{1, P(1), P^2(1), \ldots, \}$ and $x_i = P^{i-1}(1)$. We induct to show that $x_i = i$ for all $i$. Base cases: $x_1 = 1$ is obvious. Now we show $x_2 = 2$, which is the same as $P(1) = 2$. Suppose not and there existed a prime $p\mid P(1) - 1$. We see that $\{1, P(1), \ldots, \}$ is always $1\pmod p$, so it can't be divisible by $p$, contradiction. Therefore $P(1) = 2$. Inductive step: Suppose it was true for all $i \le n$, for some $n\ge 2$. Then we have $P^0(1) =1, P(1) = 2, P^2(1) = 3, \ldots, P^{n-1}(1) = n$. Notice that the sequence $\{1, P(1), P^2(1), \ldots, \}$ is periodic modulo $P^n(1) - 1$ with period dividing $n$, which means it must be $0\pmod{P^n(1) - 1}$ at some point. Since $1,\ldots, n-1$ are not $0$ modulo $P^n(1) - 1$, we have $P^n(1) \equiv 0\pmod{P^n(1) - 1}$ or $P^n(1) - 1 \mid n$. The former is clearly impossible since $P^n(1) > n \ge 2$. Therefore, $P^n(1) - 1\mid n$. Combined with the fact that $P^n(1) > n$, we have $P^n(1) = n + 1$, so $x_{n+1} = n +1$, which completes the induction.

only p6 i can solve Claim: $P(1) = 2$. Proof. FTSOC suppose that $p \mid P(1) - 1$. Then $P(1) \equiv 1 \pmod{p}$ so no $x_i$ is divisible by $p$, contradiction. $\blacksquare$ Now assume $P(n) = n + 1$. Then once again there must be no primes dividing $P(n + 1) - (n+1)$, so $P(n+1) = n+2$. Repeating this gives the result for all integers.

As $P(x) \in \mathbb{Z}[x]$ , so $x_{2}-x_{1}|P(x_{2})-P(x_{1})=x_{3}-x_{2}|\cdots |x_{n}-x_{n-1}|x_{t}-x_{t-1} \implies x_{\ell}-x_{\ell-1}|x_{t}-x_{t-1}$ $\forall$ $ t \geqslant \ell$. Also, there exists a term divisible by $N$ in the sequence , set $N:=x_{n}-x_{n-1}$ as $P(n)>n \implies x_{1}<x_{2}<x_{3}<\cdots x_{n} \cdots < x_{t} \cdots $ Since $\exists$ a term divisible by $x_{n}-x_{n-1}$ in the sequence it would be larger than it (since each term is positive), consider $x_{m}$ is that term. so $x_{n}-x_{n-1}|x_{m}$ and since $x_{n}-x_{n-1}|x_{m}-x_{m-1} \implies x_{n}-x_{n-1}|x_{m-1}$ continuing in this manner we can descend to this sequence $m \mapsto m-1 \mapsto m-2 \cdots n$ , so $x_{n}-x_{n-1}|x_{n} \implies x_{n}-x_{n-1}|x_{n-1} \implies x_{n}-x_{n-1} \leqslant x_{n-1} \implies x_{n} \leqslant 2x_{n-1} \implies P(x_{n-1}) \leqslant 2x_{n-1}$ which in turns gives $x<P(x) \leqslant 2x$ $\forall$ $x \in \mathbb{Z}^{+}$, now $\textcolor{red}{\mathrm{Claim:-}}$ $P(x)$ is linear. $\textcolor{blue}{\mathrm{Pf:-}}$ FTSOC , consider $\deg(P(x))>1$ , so sinc we have $x< P(x) \leqslant 2x \implies \lim _{x \rightarrow \infty} \frac{x}{x^{\deg(P(x))}} < \lim_{x \rightarrow \infty} \frac{P(x)}{x^{deg(P(x))}} \leqslant \lim_{x \rightarrow \infty} \frac{2x}{x^{\deg(P(x))}} \implies 0< \text{leading \hspace{0.1cm} term} \leqslant 0$ by squeeze theorem we get leading term of $P(x)$ is $0$ which is a contradiction , hence $\deg(P(x))$ is $1$. $\square$ Now it implies $P(x)=ax+b$ for some integers $a$ and $b$, we know that $x_{2}-x_{1}|x_{1} \implies x_{2}=2$ , so $P(1)=2 \implies a+b=2$ and $P(2)-2|2 \implies P(2)=3$ or $P(2)=4$ as $P(2)>2$ , so we get that $P(x)$ is $x+1$ or $2x$ , now since for every $N \in \mathbb{Z}^{+}$ there exist a term in the sequence divisible by $N$ but if we choose $N$ to be some odd prime , then we get a contradiction for $P(x)=2x$ , hence $P(x)=\boxed{x+1}$. $\blacksquare$

Assume contradiction. If their exists some $i$ such that $x_i > i$, then we take the smallest $i$ satisfying this condition. Then, by minimality, none of the first $i$ terms are divisible by $x_i-1$. (because $x_{i-1} \leq x_i-1$ and if equality held, then $i-1$ would have been a smaller such $i$.) Now, note that $x_i \equiv x_1 \equiv 1 \pmod{x_i-1}$, so we cycle back modulo $x_i-1$. Now obviously, $i \geq 2$, so $x_i-1 > 1$, so we get a contradiction. Therefore, there is no such $i$ and since we obviously have $x_i \geq i$ for all $i$, since $P(n) > n$ we have $x_i = i$ for all $i$, thus $P(i) = i+1$ for all positive integers $i$, and we get $P(x)-x-1$ has infinite roots and therefore is identically $0$. So, $P(x) = x+1$.

If $x_a=a$ for all integers $a\ge 1$, then $P(x)=x+1$ for all integers $x \ge 1$. We claim that if $P(x)=x+1$ for all integers $x\ge 1$, then $P(x)=x+1$. Let $Q(x)=P(x)-x-1$. Assume that $Q(x)\ne 0$. Then, $Q(x)$ has some finite degree $d$. By the Fundamental Theorem of Algebra, $Q(x)$ has $d$ roots. However, every natural number is a root of $Q(x)$. This is not possible if $d$ is finite. Therefore, $Q(x)=0$, so $P(x)=x+1$, as desired. We will now prove that $x_a=a$ for all integers $a\ge 1$. We will use strong induction. It is true for $a=1$ because $x_1=1$. For some natural number $b$, assume $x_c=c$ for all integers $1\le c\le b$. We will now prove that $x_{b+1}=b+1$. We claim that $x_{b+1}\not\equiv b\pmod{m}$ for any integer $m>b$. Assume otherwise. Then, $P(b)=P(x_b)=x_{b+1}\equiv b\pmod{m}$. This means that $x_k\equiv b\pmod{m}$ for all integers $k\ge b$. Since $x_k=k$ for all integers $1\le k\le b<m$, this means that no $x_k$ is divisible by $m$, as desired. When $b=1$, this means that $x_2=2$, because if $x_2>2$, then $x_2\equiv 1\pmod{x_2-1}$ and $x_2-1>1$, as desired. Now we assume $b\ge 2$. We claim that $x_{b+1}\equiv b+1\pmod{m}$ for all integers $1\le m\le b-1$ and $m=b+1$. Note that $P(k)=P(x_{k})=x_{k+1}=k+1$ for all integers $1\le k\le b-1$. Then, $$x_{b+1}=P(b)\equiv P(b-m)=b-m+1\equiv b+1\pmod{m}$$for integers $1\le m\le b-1$. Assume that $x_{b+1}=P(b)\not\equiv 0\pmod{b+1}$. This means that $P(\alpha)\not\equiv 0\pmod{b+1}$ for all $\alpha\not\equiv 0\pmod{b+1}$. This means that no $x_k$ is divisible by $b+1$. Therefore, $x_{b+1}\equiv 0\pmod{b+1}$, proving our claim. By Chinese Remainder Theorem, $x_{b+1}\equiv b+1\pmod{\text{lcm}(1,\dots,b-1,b+1)}$. If $x_{b+1}>b+1$, then $x_{b+1}\ge \max(\lceil b+1+\frac{b^2-1}2\rceil, 6)$, so $x_{b+1}\equiv b\pmod{x_{b+1}-b}$ and $x_{b+1}-b>b$. Therefore, $x_{b+1}=b+1$, as desired.