Problem

Source: ELMO 2019 Problem 1, 2019 ELMO Shortlist N1

Tags: number theory



Let $P(x)$ be a polynomial with integer coefficients such that $P(0)=1$, and let $c > 1$ be an integer. Define $x_0=0$ and $x_{i+1} = P(x_i)$ for all integers $i \ge 0$. Show that there are infinitely many positive integers $n$ such that $\gcd (x_n, n+c)=1$. Proposed by Milan Haiman and Carl Schildkraut