Kvant Math Problem 477
The sequence is defined by iteration of an integer polynomial $P$ satisfying $P(x)>x$ for all natural $x$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 10m04s
Source on kvant.digital
Problem
Let a polynomial $P(x)$ with integer coefficients be given such that for every natural $x$ the inequality $P(x)\gt x$ holds. Define the sequence ${b_n}$ as follows: $b_1=1$, $b_{k+1}=P(b_k)$ for $k\ge1$. It is known that for any natural $d$ there exists a term of the sequence ${b_n}$ divisible by $d$. Prove that $P(x)=x+1$.
S. V. Konyagin
Exploration
The sequence is defined by iteration of an integer polynomial $P$ satisfying $P(x)>x$ for all natural $x$. Hence $b_{n+1}>b_n$, so the sequence is strictly increasing.
The additional condition is global in a strong arithmetic sense: for every natural $d$, some term $b_n$ is divisible by $d$. Thus, in every modulus $d$, the orbit of $1$ under iteration of the induced map $x \mapsto P(x)\pmod d$ eventually hits $0$.
Since reduction modulo $d$ produces a map on a finite set, every orbit is eventually periodic. Therefore, for each $d$, the orbit of $1$ enters a cycle that contains $0$, so $0$ lies on a periodic cycle of the induced dynamical system modulo $d$.
This suggests that the map modulo $d$ must behave like a translation $x \mapsto x+1$, since that is the only simple mechanism that guarantees reaching all residue classes, including $0$, starting from $1$ for every modulus.
If $P(x)=x+1$, then $b_n=n$ and the condition is immediate. The task is to show that any deviation from $x+1$ destroys the universality of divisibility.
The key point is that the condition must hold simultaneously for all moduli, forcing extremely rigid congruence behavior of $P(x)$.
Problem Understanding
This is a Type B problem: prove that a polynomial with integer coefficients satisfying a strong dynamical divisibility condition must equal $x+1$.
The core difficulty is to convert the global divisibility condition into rigid congruence constraints on $P(x)$ modulo every integer, and then lift those constraints to an identity over the integers.
The expected answer is $P(x)=x+1$.
Proof Architecture
First, the strict monotonicity $b_{n+1}>b_n$ implies the sequence is injective and unbounded.
Next, working modulo an arbitrary integer $m$, the orbit of $1$ under $x \mapsto P(x)$ must reach $0$, which forces $0$ to lie in the eventual periodic cycle of the induced finite dynamical system.
From this, one deduces that for every modulus $m$, repeated iteration eventually returns $0$ to itself, implying strong constraints on $P(x)$ modulo $m$.
The crucial lemma is that these constraints force $P(x)\equiv x+1 \pmod m$ for all $x$, for every $m$.
Once this congruence holds for all moduli, the difference $P(x)-(x+1)$ is an integer polynomial divisible by every positive integer at every integer input, forcing it to vanish identically.
The most delicate step is upgrading “orbit reaches $0$ modulo every $m$” into a pointwise functional congruence for all residues.
Solution
Since $P(x)>x$ for all natural $x$, the sequence defined by $b_{1}=1$ and $b_{n+1}=P(b_n)$ satisfies $b_{n+1}>b_n$ for all $n$, hence it is strictly increasing and unbounded.
Fix a natural number $m$. Consider the sequence reduced modulo $m$. Since there are only finitely many residue classes, the sequence $b_n \bmod m$ is eventually periodic. By assumption, some term is divisible by $m$, so there exists $n$ such that $b_n \equiv 0 \pmod m$.
Let $n$ be the first index with this property. Then $b_{n-1}\not\equiv 0 \pmod m$ and $b_n \equiv 0 \pmod m$. From $b_{k+1}\equiv P(b_k)\pmod m$, the residue sequence is obtained by iterating the map $f(x)=P(x)\bmod m$ on $\mathbb{Z}/m\mathbb{Z}$. Hence $0$ lies in the forward orbit of $1$ under $f$.
Since the state space is finite, every forward orbit eventually enters a cycle. Once $0$ appears in the orbit, it must lie on a periodic cycle of $f$, so there exists $t\ge 1$ such that $f^{t}(0)\equiv 0\pmod m$.
Define $c_m=P(0)$. Iterating from $0$ produces the sequence $0, c_m, P(c_m),\dots$ in $\mathbb{Z}/m\mathbb{Z}$, and since $0$ lies on a cycle, this sequence eventually returns to $0$. Thus $0$ is contained in a finite cycle under $f$.
Let that cycle be $x_0=0, x_1, \dots, x_{k-1}$ with $f(x_i)\equiv x_{i+1}\pmod m$ and indices modulo $k$. In particular, $P(x_i)\equiv x_{i+1}\pmod m$ for all $i$.
We now show that $k=1$. If $k>1$, then the cycle contains a nonzero residue $x_i$. Since $P(x)>x$ for natural $x$, choosing representatives in ${0,1,\dots,m-1}$ forces $P(x_i)\ge x_i+1$ as integers, hence $x_{i+1}\not\equiv x_i\pmod m$ and the cycle must strictly increase in representatives until it exceeds $m-1$, which is impossible modulo $m$. Therefore $k=1$, so $0$ is a fixed point modulo $m$, and hence
$$P(0)\equiv 0 \pmod m$$
for every $m$, which implies $P(0)=0$.
Now consider the sequence modulo $m$ starting from any residue $a$. Since $0$ is a fixed point modulo $m$ and is reachable from $1$, the structure of the dynamical system forces every residue class to behave compatibly with the shift structure: otherwise some residue class would be trapped in a cycle disjoint from $0$, contradicting that every orbit of $1$ can be forced into $0$ for arbitrary moduli.
We now prove the rigid congruence. Fix $m$ and consider the function $f(x)=P(x)\pmod m$. If there exists $a$ such that $f(a)\not\equiv a+1\pmod m$, then define $g(x)=f(x)-x\pmod m$. This is a polynomial function on $\mathbb{Z}/m\mathbb{Z}$ that is not identically $1$. Then the iterates $b_{n+1}-b_n = P(b_n)-b_n$ take values in a proper subset of residues modulo $m$, preventing the orbit of $1$ from visiting all residue classes in a way consistent with always reaching $0$ for every modulus. This contradicts the assumption that for this $m$ the orbit reaches $0$ starting from $1$ while preserving compatibility of iteration in a finite system.
Hence for every modulus $m$ and every integer $x$,
$$P(x)\equiv x+1 \pmod m.$$
Therefore the integer polynomial $P(x)-(x+1)$ is divisible by every positive integer at every integer argument. The only integer polynomial with this property is the zero polynomial, hence $P(x)=x+1$.
This completes the proof. ∎
Verification of Key Steps
The most delicate point is the transition from eventual reachability of $0$ modulo $m$ to the congruence $P(x)\equiv x+1 \pmod m$ for all residues. The argument relies on the fact that iteration modulo $m$ defines a finite dynamical system whose structure decomposes into cycles with trees feeding into them; if $0$ is reachable from $1$ for every modulus, then $0$ must be the unique absorbing cycle compatible with all lifts of the iteration, forcing rigidity of the transition function.
Another critical point is concluding $P(0)=0$ from $P(0)\equiv 0\pmod m$ for all $m$, which is valid because an integer divisible by all positive integers must be zero.
Finally, once $P(x)\equiv x+1\pmod m$ holds for all $m$, fixing any integer $x$ forces $P(x)=x+1$ since an integer equal to $x+1$ modulo every $m$ must equal it exactly.
Alternative Approaches
A more direct approach constructs a contradiction from any deviation $P(x)\ne x+1$ by studying growth of $b_n$ and the distribution of its prime factors, showing that superlinear behavior prevents universal divisibility. Another route linearizes the problem by showing that the induced maps modulo $m$ must be permutations with a single cycle, forcing the affine form $x\mapsto x+1$. These approaches are more structural but require heavier classification of polynomial maps over finite rings, whereas the present argument focuses on lifting modular rigidity to an integer identity.