$\textbf{Lemma.}$ The sequence $(x_n)_{n\ge 0}$ is a Merssene sequence i.e. $\gcd(x_m;x_n)=x_{\gcd(m;n)}$ for all $m,n\ge 0$ (under the convention $\gcd(0;0)=0$, although we won't need it in our solution). $\textbf{Proof:}$ First we prove $a|b$ implies $x_a|x_b$. Indeed, let $b=an$ and notice that $x_a=x_a-x_0|P^k(x_{a})-P^k(x_0)=x_{a+k}-x_k$. From here we deduce that $x_a|x_{(k+1)a}-x_{ka}$ for all $k\ge 1$ and a straightforward induction gives $x_a|x_{ka}$, for all $k\ge 1$. Now let's prove if $d$ divides $x_m$ and $x_n$, it also divides $x_{\gcd(m;n)}$. This is enough in order to prove the lemma. W.l.o.g let $m\ge n$. From the first paragraph, $x_n|x_m-x_{m-n}$, so $d|x_{m-n}$ and $d|x_n$. Repeat this and note that it is just the Euclidian Algorithm in order to conclude that $d|x_{\gcd(m;n)}$. $\blacksquare$ Back to the problem. Suppose by contradiction that for some $N$ we have $\gcd(x_n;n+c)\ge 2$, for all $n\ge N$. We split the solution in $2$ cases: $\textbf{Case 1.}$ $c$ is even. We have $\gcd(c-1,2)=1$. Take a huge prime $p$ (greater than $N+c$) such that $p\equiv 2(\mod c-1)$. This is possible by Dirichlet's Theorem. What we supposed gives that $p|x_{p^k-c}$ for all $k\ge 1$. We will consider only the situations $k=1$ and $k=p+1$. $\textbf{Claim.}$ $\gcd(p-c;p^{p+1}-c)=1$. $\textbf{Proof.}$ Let $q$ a prime divide both so that $q|p-c$ and $q|p^{p+1}-c$. In particular $q\le p-2$. Substracting gives $q|p^p-1$, so $ord_q(p)|p$. This means $ord_q(p)$ is either $1$ or $p$. The former would give $q|p-1$, which further gives $q|c-1$. However, from the way we chose $p$ we get $\gcd(p-1;c-1)=1$, while the latter would give $q$ as a common factor for them a contradiction! The second possibility would give $p|q-1$ by Fermat's Little Theorem, impossible since $q\le p-2$. The claim is now proved. $\blacksquare$ Toghether the claim and the lemma give that $p|x_{\gcd(p^{p+1}-c;p-c)}$ or $p|x_{1}=1$, a contradiction! $\textbf{Case 2.}$ $c$ is odd. Again, what we supposed gives $2|x_{2^k-c}$, for all very large $k$. Take a prime $r>2^k-c$. $\textbf{Claim.}$ $\gcd(2^k-c;2^{k+r}-c)=1$. $\textbf{Proof.}$ Suppose $q$ is a common prime divisor or them. Therefore $q|2^k-c$ and $q|2^{k+r}-c$ and substracting we obtain $q|2^r-1$, since obviously $q$ is odd. Thus $ord_q(2)|r$, so $ord_q(2)$ is either $1$ or $r$. The former translates into $q|2-1$, vacuously false, while the latter, by Fermat's Little Theorem, gives $r|q-1$, so $r<q-1<2^k-c$, since $q|2^k-c$. This is a contradiction! $\blacksquare$ Now, this claim and the initial lemma give $2|x_{\gcd(2^k-c;2^{k+r}-c)}=x_1=1$, again a contradiction! Therefore, we supposed wrong, hence the conclusion follows.

WLOG assume that there is an $M$ for which $x_i\neq 0$ for any $i\ge M,$ consider only such indices from this point. $$x_i-0 \mid P^j(x_i)-P^j(0) \implies x_{i+j} \equiv x_j \pmod{x_i} \implies x_i \equiv x_{i-kj} \pmod{x_k}$$For any $k$ such that $i\ge kj.$ Suppose FTSOC that $\gcd(x_n, n+c) \neq 1$ for any big enough $n.$ Pick $n=p^e-c$ for some big enough prime $p$, note that this implies that $p\mid x_{p^e-c}$ for all $e\ge 1\implies $ $$x_{p^e-c} \equiv x_{p^e-c-(p-c)\frac{p^e-c^e}{p-c}} \pmod{x_{p-c}} \implies p \mid x_{p-c} \mid x_{p^e-c}-x_{c^e-c} \implies p \mid x_{c^e-c}$$Pick an $e$ such that $c^e-c>M$ and a $p$ for which $p>x_{c^e-c}+M$ and we achieve a contradiction.

Solution. Note that $x_i = P^i(0) = \underbrace{P(P(...(}_{\text{i times}} 0)...))$. Lemma. Suppose $f$ is an integer coefficient polynomial, then $f(a) \equiv f(b)\mod m$ if $a\equiv b\mod m$. (Proof): We know that $m\mid a-b\mid f(a)-f(b)$ and we are done. $~\square$ Claim 1. Suppose $p$ is a prime and if $p\mid x_r$ and $p\mid x_s$ then $p\mid x_{|r-s|}$. (Proof): Without loss of generality, $r\geq s$. Therefore we have \[0 \equiv P^r(0)\equiv P^{r-s}(P^s(0))\equiv P^{r-s}(P^s(0)\mod p) \equiv P^{r-s}(0) \mod p.\]Therefore $p\mid x_{r-s}$. $~\square$ Main Problem. Suppose for infinitely many primes $p$, $p\nmid x_{p-c}$, then $\gcd(x_{p-c},p-c+c) = \gcd(x_{p-c},p) = 1$ and we would be done by choosing those $p-c$'s. Therefore we now assume that only for finitely many primes $p$, $p\nmid x_{p-c}$, or $p\mid x_{p-c}$ for all primes $p\geq p_0$ for some large $p_0$. Now for infinitely many primes $p\geq p_0$ if we have $p\nmid x_{p^2-c}$, then $\gcd(x_{p^2-c},p^2-c+c) =\gcd(x_{p^2-c},p^2) = 1$ and we would be done by just choosing those $p^2-c$'s. Therefore for infinitely many primes $p\geq p_1\geq p_0$ for some large $p_1$ we have $p\mid x_{p^2-c}$. But as $p\geq p_0$, we have $p\mid x_{p-c}$. Now from Claim 1, \[0\equiv x_{p^2-c} \equiv x_{(p^2-c)-(p+c)(p-c)} \equiv x_{c^2-c} \pmod p\]for all primes $p\ge p_1$. But $x_{c^2-c}$ is a constant and it is divisible by infinitely many primes (all primes greater than $p_1$), so $x_{c^2-c} = 0 = x_0$, so the sequence $<x_n>$ is periodic and repeats in $c^2-c$, i.e. $x_t = x_{t+c^2-c}$ of any $t$. Now $x_1 = 1$, so $x_{1+k(c^2-c)} = 1$ for any natural $k$. Therefore $\gcd(x_{1+k(c^2-c)},1+k(c^2-c) + c) = \gcd(1, 1+k(c^2-c) + c)) = 1$ for any $k$ and we are done. $\blacksquare$

Wowww! Really elegant and beautiful solutions

@2above I also have the same solution as of the dark prince

Let $P^k(x)=\underbrace{P(P(P(\cdots P}_{k \text{ times}}(x)))),$ where we define $P^0(x)=x.$ So we can see that $x_i=P^i(0).$ Now, assume on the contrary that there are only finitely many positive integers $n$ satisfying the condition. Then we must have that for some $N \in \mathbb{N},$ $$\text{gcd}(x_{n},n+c)>1 \quad \forall \text{ }n>N$$ Take $n=p-c$ for some prime $p$ greater than $c$ such that $p-c>N.$ Then $$1<\text{gcd} (x_n,n+c)=\text{gcd}(x_{p-c},p) \implies p|x_{p-c} \quad \forall \text{ primes }p>c+N$$ Take $n=p^2-c$ for a prime $p>N+c.$ Then we get $$1<\text{gcd}(x_n,n+c)=\text{gcd}(x_{p^2-c},p^2) \implies p|x_{p^2-c} \quad \forall \text{ primes }p>c+N$$ Now note that $$P^{y}(0) \equiv P^x(0) \pmod{p} \implies P^{y-kx}(0) \equiv P^x(0) \pmod{p} \quad \forall \text{ naturals }y>kx$$Now for all primes $p>c+N,$ using the two results above we get \begin{align*} P^{p^2-c}(0) \equiv 0 \equiv P^{p-c}(0) \pmod{p} \\ \implies P^{(p^2-c)-(p+c)(p-c)}(0) \equiv P^{p-c}(0) \equiv 0 \pmod{p} \\ \implies P^{c^2-c}(0) \equiv 0 \pmod{p} \end{align*}But $x_{x^2-x}$ is a constant, say $k.$ Hence $p|k$ for all primes $p>N+c$ so $p \le k$ if $k \ne 0$ for all primes $p>N+c,$ clearly a contradiction. If $k=0$ on the other hand, then $x_{c^2-c-1}=1$ as $P(0)=1,$ and so $x_{k(c^2-c)}=1$ for all $k \ge 1.$ Since $c \ne 1,$ hence $k(c^2-c)$ can be as large as possible and so using our assumption we get $\gcd (x_{k(c^2-c)},n+c)>1,$ a contradiction. $\blacksquare$ $\blacksquare$

Maybe I shouldn't posting this because this is again all about $x_{c^2-c}$, but still I will

Take some prime $ p > c $, for which $ gcd(p-1,c-1) = 1$. Let $y_i$ be the residue of $x_i$ $mod$ $p$. If $y_i \cong 0 ( mod p)$ is true only for $ i = 0 $ then we can set $ n = p^{a} - c $ for any natural number $a$ , so $gcd(x_n,n+c) = gcd(x_n,p^a) = 1$. If not , denote the minimal $t > 0$ , $y_t \cong 0 (mod p)$ by $ T $. Clearly $y_i$ has period $T$ ( if $ y_l = 0$ then $l \cong 0 (mod T)$ ) and $T \leq p$. If $ T = p$ we set $ n = p^{a} - c$ for any natural number $a$ , if $gcd(x_n,n+c) \neq 1$ then $y_n = 0$ , but $y_{p^{a} - c} = y_{p-c}$ which clearly cannot be $0$ because of the minimality of $T$. If $T < p$ , because $c > 1$ and $ gcd(p-1,c-1) = 1$ we can find some $a$ for which $p^{a} \ncong c ( mod T)$ , then we set $ n = p^{a + b*ord_T(p)} - c$ for any $b$. If $gcd(x_n,n+c) \neq 1$ then $y_n = 0$ , but $ y_{p^{a + b*ord_T(p)} - c} = y_{p^a - c} \neq 0$ , because $p^{a} \ncong c ( mod T)$

Here's a solution that's very different in spirit:

We consider two cases: Case 1: Suppose there exist $i\ge 0$ so that $|x_{i+1}-x_{i}|>1$. Now note that for any nonnegative integer $i$, $x_i-0|P(x_i)-P(0)\implies x_i|x_{i+1}-1.$ Further, we have $x_{i+1}-x_i|P(x_{i+1})-P(x_i)\implies x_{i+1}-x_i|x_{i+2}-x_{i+1}.$ Similarly $$x_{i+2}-x_{i+1}|x_{i+3}-x_{i+2}\implies x_{i+1}-x_i|x_{i+3}-x_{i+2}\implies x_{i+1}-x_i|x_{i+3}-x_{i}=(x_{i+3}-x_{i+2})+(x_{i+2}-x_{i+1})+(x_{i+1}-x_i),$$and using this argument over and over, $x_{i+1}-x_i|x_{m}-x_i$ for any $m\ge i+1$. Now choose $n=|x_{i+1}-x_i|^N-c$; for large enough $N$, $n\ge m$. Now if $p$ divides $x_n$ and $n+c$, then $p|(x_{i+1}-x_i)^N\implies p|x_{i+1}-x_i|x_m-x_i$, so $p|x_i|x_{i+1}-1$ and $p|x_{i+1}$, giving $p|1$, contradiction. Thus $\gcd (x_n,n+c)=1$. Since any sufficiently large $N$ would work, we have found infinitely many such $n$. Case 2: In case $|x_{i+1}-x_{i}|\le 1$ for all $i$, first assume the sequence $\langle x_i\rangle_{i=0}^\infty$ has infinitely many distinct elements. Thus by pigeonhole principle, there exists $k\in \{0,1,-1\}$ $P(x_i)-x_i=x_{i+1}-x_i=k$ for infinitely many $i$. Thus $P(x)\equiv x+k$, and since $P(0)=1$, $P(x)\equiv x+1$. In this case $x_n=n$, so it suffices to choose $n$ so that $\gcd (n,c)=1$. If the sequence $\langle x_i\rangle_{i=0}^\infty$ has only finitely many elements, then there are again two cases: if $0$ appears only finitely many times, the it's enough to choose $n=p-c$ for some large prime $p$ that doesn't divide any of the non-zero elements of the sequence. If $0$ occurs infinitely many times, the the number next to $0$ will be $1$, and the $n'$s corresponding to those $1$'s all work.

$\textbf{Solution 1.}$ Firstly, consider a sequence of integers $\{a_n\}_{n \ge 1}$ satisfying the property $$ \text{gcd} (a_n , a_m ) = a_{\text{gcd} (n,m)}$$These sequences are well known and are called $\textbf{Mersenne Sequences}$. Now we present the following claim : $ $ $\textbf{Lemma}$ : The sequence $\{x_n\}$ is a $\textbf{Mersenne Sequence}$. Proof : Let $g = P^d$ be the composite of $P$ with itself $d$ times.If $m = d\cdot u$ and $n=d \cdot v$, with $\text{gcd} (u,v) = 1$, are any postive integers, note that $x_n = g^v (0)$ and $x_m = g^u (0)$. Also, $a_d = g(0)$.So, it is enough to prove that for any $g \in \mathbb{Z} [X]$ and any $\text{gcd} (u,v) = 1$, we have that $$ \text{gcd} ( g^u (0) , g^v (0) ) = g(0)$$Clearly, for any polynomial $t \in \mathbb{Z} [X]$, $t(0) \mid t^l(0) , \forall l \in \mathbb{Z^+}\dots (i)$ Using the above remark for $t = g$, we get that $g(0) \mid \text{gcd} (g^v(0) , g^u (0))$. $ $ Conversely, let $y = \text{gcd} (g^v(0) , g^u (0))$. So by $(i)$, let $t = g^u$ and $t= g^v$, we obtain : $y \mid g^{Au} (0)$, $y \mid g^{Bv}(0)$, for some $A,B$. Taking $Au + 1 = Bv$, we obtain $$ y \mid g(g^{Au}(0)) ; y \mid g^{Au} (0) \implies y \mid g(0)$$Hence the lemma holds. $ $ Now that we have obtained a good way of characterizing the sequence $\{x_n\}$, let's finish this of! $\textbf{Lemma 2}$ : There are infinitely many integers $n$ such that $\text{gcd}(x_n , n+c) = 1$ $ $ Proof : Assume for the sake of contradiction that there are only finitely many such $n$'s. Thus, $\exists n_0 \in \mathbb {Z^+}$ such that $\forall M > n_0 , \text{gcd} (x_M , M+c) > 1$. Now, pick a prime $p > n_0$ such that $p \nmid c$ and let $n = p-c$. Thus, $p \mid x_{p-c}$. Also,$$n = p^2 -c \implies p \mid x_{p^2-c} \iff p \mid \text{gcd} ( x_{p-c} , x_{p^2-c}) \overset{\text{Lemma 1}}{\iff} p \mid x_{\text{gcd} (p-c,p^2-c)}$$The rest is a simple analysis of $\text{gcd} (p-c , p^2-c) $ for an infinite values of $p$, which gives a contradiction.

Let $c-1=2^u\cdot v$ with $v=$odd. From Dirichlet's Theorem and CRT we can pick $p$ a prime bigger than $c$ and bigger than $P(1)$ with $p\equiv 2 (mod\ v)$ and $p\equiv 3(mod 4)$ . Now we look at the sequence $(x_i)_{i\geq 0}$ mod $p$ .If there is no number $t>0$ such that $p\mid x_t$ then just take $n=p^k-c$ for any positive integer $k$ .If there is a number $t>0$ such that $p\mid x_t$ then pick the smallest such $t$ denoted $T$. Obviously the sequence has period $T>1$ mod $p$. If $T>p$ then between $x_1,x_2,..,x_T$ there are 2 equal mod p let's call them: $x_a,x_b$ with $a<b$.This means that from $x_a$ the sequence is periodic with period $b-a$ so $p\mid x_{T+a-b}$. But $0<T+a-b<T$ and this is a contradiction with the definition of $T$. If $T=p$ we just pick $n=p^k-c$ for any positive integer $k$, because $p\mid x_n \iff p\mid n$ and as $p>c>0$ we are done. If $T<p$ we have two cases: Case 1: $T\nmid c-1$ then we pick $n=p^{k\cdot\phi(T)}-c$ for any positive integer $k$. Case 2: $T\mid c-1$ and $T\nmid p-1$ then $T\nmid p-c$. We can thus take $n=p^{k\cdot\phi(T)+1}-c$ for any positive integer k. If $T\mid c-1$ and $T\mid p-1$.Let $q=prime$ , $q\mid T$. If q=odd then $q\mid v$ and $q\mid p-1$ a contradiction.Thus $T=2^a$ but $T\mid p-1$ and $v_2(p-1)=1$ so $T=2$.Therefore $p\mid P(1)$ a contradiction with $p > P(1)$

Let $P(x)$ be a polynomial with with integral coefficients. Define the iteration sequence $(x_n)_{n \ge 0}$ recursively by $x_0 = 0$ and $x_{n + 1} = P(x_n)$. Given $c \in \mathbb{Z}$, we say that $\mathcal{P}(P, c)$ holds if there are infinitely many integers $n \ge c$ such that $\text{gcd}(x_{n - c}, n) = 1$. We are asked whether $\mathcal{P}(P, c)$ always holds when $P(0) = 1$ and $c \ge 1$. In the following, we will answer the more general question for which pairs $(P, c) \in \mathbb{Z}[x] \times \mathbb{Z}$ property $\mathcal{P}(P, c)$ holds. The main idea is to consider values of $n$ for which we can control the $\text{gcd}$ most easily. The simplest case is when $n = p$ is a prime number; then $\text{gcd}(x_{p - c}, p) = 1$ if and only if $p \nmid x_{p - c}$. For example, if we can show that there are infinitely many primes $p$ such that $p \nmid P(m)$ for all $m \in \mathbb{Z}$, then $\mathcal{P}(P, c)$ holds for all $c$. Using more advanced theory, one can show that this works whenever $P$ is irreducible (this uses Galois theory, a weak version of the Chebotarev density theorem and the fact that a finite permutation group all of whose elements have a fixed point must be trivial). But there are polynomials that have roots modulo all primes or at least all but finitely many primes. (Linear polynomials for example, but also polynomials like $(x^2 + 1)(2x^2 + 1)(-2x^2 + 1)$; this follows from the multiplicativity of the Legendre symbol.) To keep things elementary, we will consider two values of $n$ associated to $p$. This reason why this works is that we have a good chance of deducing strong restrictions on $p$ when $p$ divides two of the $x_n$. This is captured by the following result. Lemma 1. Let $P$ and $(x_n)_{n \ge 0}$ be as above and let $p$ be a prime number. 1. There is a unique number $m = m(P, p) \ge 0$ such that $p \mid x_n$ if and only if $m \mid n$. ($m = 0$ is possible; then $p \mid x_n$ only for $n = 0$.) 2. If $p \mid x_m$ and $p \mid x_n$, then $p \mid x_l$ whenever $l$ is a multiple of $\text{gcd}(m, n)$. Proof. Exercise. $\square$ For the most complicated case in the proof of the theorem below, we also need the following. Lemma 2. Let $P$ and $(x_n)_{n \ge 0}$ be as above and let $p \ge 3$ be a prime number. If $x_n \neq 0$ and $p^2 \mid x_n$, then $v_p(x_{pn}) \le v_p(x_n) + 1$. Here $v_p(m)$ denotes the exponent of the highest power of $p$ dividing $m$. Proof. Let $P_n$ be the $n$th iterate of $P$ and define $h(x) = x_n^{-1}P_n(x_nx) = 1 + ax + \text{higher terms}$. Consider the $p$th term of the iteration sequence associated to $h$. $\square$ Now we can state and prove the main result. Theorem 3. Let $P \in \mathbb{Z}[x]$ and $c \in \mathbb{Z}$. Define $(x_n)_{n \ge 0}$ by $x_0 = 0$ and $x_{n + 1} = P(x_n)$. Then $\mathcal{P}(P, c)$ holds except in the following cases (where it does not hold). 1. $x_1 = 0$. 2. $x_1$ is even, $x_2 = 0$, and $c$ is odd. 3. $P(x) = x + a$ with $a \in \mathbb{Z}$ and $c = 0$. In particular, $\mathcal{P}(P, c)$ holds whenever $P(0) = 1$ and $c \ge 1$. Proof. We first consider the situation when $x_n = 0$ for some $n > 0$. Then the sequence $(x_n)$ is periodic with some minimal period $m > 0$. It is clear that in cases (1) and (2) $\mathcal{P}(P, c)$ does not hold. If $m = 2$ and $x_1$ is odd or $c$ is even, then there will be infinitely many odd $n$ such that $n + c$ is coprime with $x_1 = x_n$, so $\mathcal{P}(P, c)$ holds. So we can assume that $m \ge 3$. Then there is $j \in \{1, 2, \ldots, m - 1\}$ such that $\text{gcd}(m, c + j) = 1$. Then $n = c + j + lm$ is always coprime with $m$ for all $l \in \mathbb{Z}_{\ge 0}$ and we can choose $l$ so that $\text{gcd}(x_j, n) = 1$. Adding multiples to $|x_j|$ to $l$ gives us infinitely many $n$ with the required property (note that $x_{n - c} = x_j)$. We can now assume that $x_n \neq 0$ for all $n > 0$. If $c \not\in \{0, 1\}$, then there are only finitely many primes dividing $c$ or $x_{|c - 1|} \neq 0$. If $p$ is a prime that is not one of these exceptions, then we claim that $\text{gcd}(x_{n - c}, n) = 1$ for at least one $n \in \{p, p^2\}$. Assume otherwise. Then $p \mid x_{p - c}$ and $p \mid x_{p^2 - c}$, so by Lemma 1 (2), $p \mid x_l$ whenever $l$ is a multiple of $\text{gcd}(p - c, p^2 - c)$. Since $(p^2 - c) - (p + 1)(p - c) = p(c - 1)$ and $p \nmid p - c$, we see that $\text{gcd}(p - c, p^2 - c)$ divides $c - 1$. So $p \mid x_{|c - 1|}$, which contradicts our assumption on $p$. Since there are infinitely many suitable $p$, we also get infinitely many $n$ such that $\text{gcd}(x_{n - c}, n) = 1$. Now we consider the case $c = 1$. If there are infinitely many primes $p$ such that $p \nmid x_{p - 1}$, then we are OKAY. So assume that for all but finitely many primes $p$, we have that $p \mid x_{p - 1}$. Let $q$ be such a prime, with $q \nmid x_1x_2$. Then $m = m(P, q) \ge 3$ and divides $q - 1$. Let $p$ be another prime such that $p \nmid x_{q - 1}$ and $p \not\equiv 1\, \text{mod}\,m$. (One can vary Euclid's argument to show that infinitely many primes with the latter property exist when $m \ge 3$: Let $p_1, \ldots, p_n$ such primes (that do not divide $m$) and consider $(p_1 \ldots p_n)^{\varphi(m)} + 1$, where $\varphi$ is the Euler totient function.) We claim that $\text{gcd}(x_{pq - 1}, pq) = 1$. If $p \mid x_{pq - 1}$, then $p \mid x_{p - 1}$ implies that $p \mid x_{q - 1}$ by Lemma 1 (2), a contradiction. If $q \mid x_{pq - 1}$, then we find in the same way that $q \mid x_{p - 1}$, but $m \nmid p - 1$, so this is another contradiction. So we get infinitely many $n = pq$ such that $\text{gcd}(x_{n - 1}, n) = 1$. (If $x_1 = 1$, or more generally, $x_1$ is odd, there is a simpler argument using $q = 2$.) It remains to consider $c = 0$. Here we have to show that the polynomials $P(x) = x + a$ are the only exceptions. The fact that exceptions exist makes this the most difficult case. We assume that $\mathcal{P}(P, 0)$ does not hold. This implies that $p \mid x_p$ for all but finitely many primes $p$. Since $x_1 \neq 0$, this means that $m(P, p) = p$ for all but finitely many $p$. Let $a = x_1 = P(0) \neq 0$ and define $g(x) = a^{-1}P(ax) \in \mathbb{Z}[x]$; then $g(0) = 1$. Define $(y_n)$ as the iteration sequence for $g$; then $x_n = ay_n$ for all $n \ge 0$. Also, $m(g, p) > 1$ for all primes $p$. We can then deduce that for almost all primes $p$ we have that $x_{p^e}$ is $\pm a$ times a power of $p$ for all $e \ge 1$. (We have to exclude the finitely many primes $p$ for which there exists another prime $q$ with $m(g, q) = p$.) We observe that the sequence $(x_n)$ must be unbounded, since otherwise it would be eventually periodic and so its terms could involve only finitely many prime divisors. It is not hard to see that when $|x|$ is sufficiently large (depending on $P$), $|P(x)| \ge {2\over3}|\lambda x|^d$ where $d$ is the degree of $P$ and $\lambda$ is the leading coefficient of $P$. Note that Lemma 2 implies that $|x_{p^2}| \le p|x_p|$ when $p^2 \mid x_p$. If $d \ge 2$, then $(x_n)$ grows too fast to be compatible with this, and the same still holds when $d = 1$ and $|\lambda| \ge 2$. So there are only the three possibilities $P(x) = x + a,\,a,\,-x + a$. The first is listed in (3), it is easy to see that the second satisfies $\mathcal{P}(P, 0)$, and the last has $x_2 = 0$. $\square$

GetOffTheInternet wrote: Proof. Exercise. $\square$ Huh?

MarkBcc168 wrote: $f^{(c^2-c)}(0)$ So that's why $c>1$! I did the $n=p^m-c$ solution, and the condition $c\neq 0$ was enough. (I think)

Let me also give some commentary, for those interested in someone's thought process approaching a problem like this. My first instinct was that it might be impossible to provide a proof. In mathematics in general, but number theory especially, many natural questions are simply so difficult that they are out of reach given the present state of mathematical knowledge. A favorite example of mine is the problem of Fibonacci primes---are there infinitely many Fibonacci numbers that are also prime numbers? The answer to this question is not known, and it is considered so hard that no one has any hope of seeing it solved in the near future. Our question though deals, at least indirectly, with prime factors of the sequence $x_n$, which are extremely difficult to get a handle on. So lots of natural questions about them are also out of reach. For instance, are infinitely many of the $x_n$ prime? This is almost certainly harder than the Fibonacci problem mentioned above. But the key aspects of our question that make it approachable is that we are taking the $\text{gcd}$ of the $x_n$ with the corresponding term of an "easy" sequence, namely the sequence $c,\, c+1,\, c+2,\ldots$. And we only request knowledge about an infinite set of $n$. Doubtless the full set $\{n : \text{gcd}(x_n, n_c) = 1\}$ is rather large in general. But here a very thin set of $n$'s will do. Now on to an example---for me, this is the first step in really digesting any mathematical question. Let $P(x) = x^2 + 1$, and $c = 2$. The first few numbers we are interested in are $\text{gcd}(1,3),\, \text{gcd}(2,4),\, \text{gcd}(5,5),\, \text{gcd}(26,6),\, \text{gcd}(677,7)$. Clearly when $n$ is even, both $x_n$ and $n + c$ are even, so the $\text{gcd}$ must exceed $1$. But the two numbers $\text{gcd}(5,5), \,\text{gcd}(677,7)$ give a promising insight---when $n+c = p$ for some prime $p$, it's sufficient for $p$ not to divide $x_n$. Now, does $7$ divide $677$? Well, no---we can just reduce $677 \text{ mod }7$ by hand and show that we don't get $0$. But there's actually an easier way, which gives a stronger conclusion---consider the entire sequence $\{x_n\}_{n \ge 1}$ modulo $7$. We get $1 \to 2 \to 5 \to 5$, and by the iterative nature of $x_n$, every term past the third is $5$. Since $0$ never appears, we have that $7$ does not divide any $x_n$. These observations pave the way for a proof. First, and crucially, note that the sequence $\{n + c\}_{n \ge 1}$ contains all but finitely many primes. So it's enough to give an infinite set of primes that do not divide any $x_n$. For $P(x) = x^2 + 1$, we can argue as follows---in order to get $0$ in the sequence $\{x_n \text{ mod } p\}_{n \ge 1}$, there has to be some number $r$ with the property that $r^2 + 1 = 0 \text{ mod }p$ (or equivalently, the polynomial $x^2 + 1$ must have a root modulo $p$). Now we use two classical results from number theory---(1) there exists no such $r$ if and only if $p$ is equivalent to $3$ modulo $4$, and (2) there are infinitely many primes that are equivalent to $3$ modulo $4$ (indeed, the set of such primes has natural density $1/2$). Essentially any number theory text will have a proof of the first result, and most likely also a proof of the second result. The second result is a special case of a famous theorem called Dirichlet's theorem on primes in arithmetic progressions. This furnishes a proof for $P(x) = x^2 + 1$ and any $c$. However, it falls apart for other choices of $P$. For example, take $P(x) = x^3 + 1$. Now we can't forbid the existence of $r$ with $r^3 + 1 = 0 \text{ mod }p$, because there exists such an $r$ in $\mathbb{Z}$ (namely $r = -1$), and so it will exist modulo every $p$. It's best to take another approach in a case like this. One can show that, if the degree of $P$ is at least two, then there are infinitely many primes $p$ such that, modulo $p$, some iterate of $f$ maps $0$ to a point $a \neq 0$ satisfying $P(a) = a$ (this is what happened in the example from two paragraphs ago). Such a prime cannot divide any $x_n$. For a fairly advanced writeup of the proof of this fact, see Lemmas 4.1 and 4.3 of the following paper https://link.springer.com/article/10.1007/s00208-010-0621-4---I've attached a copy of the paper to my post. The statements are pretty technical---perhaps some reader can provide a proof in different language in the case of interest here, namely where $P$ is a polynomial with integer coefficients whose degree is at least two. By the way, we can ask a related question by replacing the sequence $c,\, c+1, \,c+2,\ldots$ with the sequence $c,\, c+1, \,c+4, \,c+9, \,c+16,\ldots$. And now a completely different approach is required, since it remains unknown whether this last sequence contains infinitely many primes.

Solution(choosing $n$ here means that such an $n$ would have the property $x_n$ and $n+c$ are coprime, so we are "choosing" it for our purpose): Suppose there exists a prime $p$ so that $p$ does not divide $x_a$ for any positive integer $a$. Then we can choose $n=p^k-c$ for large enough $k$ to satisfy our conditions. So assume this case does not occur. So there exists a positive integer $d$ for any prime $p$ such that $p|x_d$. Let $p_e$ be the smallest such positive number, for a given prime $p$. Now as $a-b|P(a)-P(b)$ for any $P(x) \in Z[x]$, $x_{a+p_e} \equiv x_a$ mod $p$ as $P(0)=1$, so $x_{p_e+1}$ will again be $1$ mod $p$ like $x_1$ and the cycle of $x_n$ mod $p$ will repeat with period $p_e$. So $p|x_n$ if and only if $p_e|n$. Of course $p_e>1$ as $x_1=P(0)=1$ is given. Now we consider some cases for a particular prime $p$: Case 1: There exists a positive integer $k$ for which $p_e$ doesn't divide $p^k-c$: In that case, if $p|p_e$, then all positive integers have that property, otherwise if $p$ doesn't divide $p_e$, then $p^{k+n\phi(p_e)}-c$ (where we use the function $\phi(n)$ which is the number of positive integers coprime to $n$ and less than or equal to $n$) has the property for any nonnegative $n$. Either way, infinitely many such integers of the form $p^k-c$ aren't a multiple of $p_e$ and all of them work when chosen as the $n$ for which $x_n$ and $n+c$ are coprime. Case 2: For all positive integers $k$, $p_e|p^k-c$: If $p|p_e$ then $p|c$. Otherwise, if $p$ is not a divisor of $p_e$, then $p^k-c$ is always a multiple of $p_e$. Hence $p^k$ always has a constant remainder modulo $p_e$ for positive $k$. As $p$ is not a divisor of $p_e$, $p^{\phi(p_e)}$ is $1$ mod $p_e$. Hence, we can see that $p \equiv 1$ mod $p_e$ or $p_e|p-1$ and $c\equiv 1$ mod $p_e$. From our cases, we have gathered that in a "non-trivial" scenario(where you don't immediately get the solution, so we are only left to consider Case 2), either: $p|p_e$ and $p|c$ or $p_e|p-1,p_e>1$ and $p_e|c-1$ is true for any particular prime $p$. At least one of the two events occur infinitely often as there are an infinite number of primes. If the first event is the one occurring infinitely often, $c=0$ which contradicts $c>1$. So the second event occurs infinitely often. Now, collect all the infinite $p_e$ of the infinite primes $p$ for which this second case occurs. Then $c=mk+1$ for some integer $m$, where $k$ is the LCM of all the collected infinite $p_e$, if such a finite number exists. Because if it is not a finite number, then $c=1$ contradicting $c>1$. So such a $k$ exists. However it means that $x_{nk}=0$ for all nonnegative $n$ as all numbers of this form are a multiple of the infinitely many primes $p$ for which the second case occurs. However, as $P(0)=1$, it means that $x_{ak+1}=1$ for all non-negative $a$, and choosing $n=ak+1$ for non-negative $k$ works as all integers are coprime to $1$. In any case, we can generate infinitely many examples, proving the required problem statement.

Different approach: Let P(x)=a_nx^n+..+1, if |d=a1+a2+..an|>1 therefore P(x)=1[d] then choose e prime |d, we have (P(x),e^n)=1. If d=-1, then P is 2-periodic hence conclusion. If d=1, by simple induction x_n=n[2] and lemma: If x_n is periodic hence choose n+c large prime. Let G(x)=P(x)-1 then G(odd)=even, G(even)=odd. By lemma |G(x_k)|>0 forall k>2 and limG->oo. Choose the smallest k that G(x_k) has odd prime divisor e. By minimal arguement, x_1,..,x_{k-1} is not divisible by e. If there is p that k|e^p-c-s for some 0<s<k, choose m=km+s=e^p-c hence (x_n,n+c)=(x_s,e^p)=1, then choose p+t.o(k) with o-euler function hence infinite n. Thus e^p<>c+s[k] forall p but c+s miss only 1 remainder mod k for 0<s<k hence e=0,1[k]. If e=1[k] because k|e^m-c hence c=1[k]. Choose n=k^m-c, note (x_k,x_{k-1})=1 and k|x_k hence infinite n. If k|e thus k|c because k|e^m-c but e is prime, k>1 hence k=e|c. Notice there are infinte e hence absurd, thus conclusion. WHY THIS BEAUTIFUL APPROACH HAS ONLY 1 POINT BECAUSE THIS BOLD TYPING MISTAKE WHEN I WRITE k INSTEAD OF e IN MY PAPER???

Can someone please check this solution? I'm not sure if I ever invoke the condition that $c > 1$, so I'm concerned that this solution has a flaw that I'm not seeing. Thanks! We first prove an important lemma that will help us reason with the sequence $(x_n)$. Lemma: For all positive integers $m$ and $n$, we have $\gcd(x_m,x_n) = x_{\gcd(m,n)}$. Proof. We first show that \[ x_{m+n}\equiv x_m\pmod{x_n}\quad(\dagger) \]for all $m,n\geq 1$. To prove this, fix $n\geq 1$; we show $(\dagger)$ by induction on $m$. The ``base case" of $m = 0$ is easy, since it is equivalent to $x_n\equiv x_0\equiv 0\pmod{x_n}$. Then, for the inductive step, write \[ x_{m+1+n}\equiv P(x_{m+n}) \equiv P(x_m)\equiv x_{m+1}\pmod{x_n}. \]This proves $(\dagger)$. To prove the original lemma, we perform strong induction on the quantity $m+n$. The base case of $m+n=2$ is easy, since $\gcd(x_1,x_1) = x_1 = x_{\gcd(1,1)}$; the same argument implies that the lemma holds whenever $m = n$. Now for the inductive step, fix $m$ and $n$ with $m+n\geq 3$, and assume without loss of generality that $m > n$. Then $(\dagger)$ and the induction hypothesis implies that \[ \gcd(x_m,x_n) \stackrel{(\dagger)}= \gcd(x_{m-n},x_n) \stackrel{(IH)}= x_{\gcd(m-n,n)} = x_{\gcd(m,n)}. \]We are done. $\blacksquare$ We now proceed with the original problem. Suppose for the sake of contradiction that there exists some positive integer $N$ such that $\gcd(x_n,n+c) \geq 2$ whenever $n\geq N$. Let $p$ be an arbitrary prime, and let $k\geq 1$ be an arbitrary integer with $p^k \geq N + c$. Observe that \[ 1 < \gcd(x_{p^k-c},(p^k-c)+c) = \gcd(x_{p^k-c},p^k); \]as a result this greatest common divisor is divisible by $p$, meaning that $p\mid x_{p^k - c}$. Similarly, $p\mid x_{p^{k+1} - c}$. But now observe that $\gcd(p^k-c,p^{k+1}-c)$ cannot be $1$, because otherwise the Lemma tells us that \[ \gcd(x_{p^k-c},x_{p^{k+1}-c}) = x_{\gcd(p^k-c,p^{k+1}-c)} = x_1 = 1. \]This contradicts the fact that both integers are divisible by $p$. Let $p_1 < p_2 < p_3 < \cdots$ denote the sequence of positive primes in order, and set $p_0 = 1$ for convenience. We claim that $p_i$ divides $c$ for every $i\geq 0$. This gives us our desired contradiction, as $c$ cannot have infinitely many prime divisors. To prove this, we proceed by induction on $i$. The base case of $i=0$ is obvious. Now for the inductive step, write via the Euclidean Algorithm that \begin{align*} \gcd(p_n^k - c,p_n^{k+1}-c) &= \gcd(p_n^k-c,p_n^{k+1} - c - p_n(p_n^k-c))\\ &= \gcd(p_n^k-c,(p_n - 1)c). \end{align*}Let $q$ be an arbitrary prime divisor of $p_n - 1$. Observe that by our inductive hypothesis we have that $q$ divides $c$. Hence $q$ cannot divide $p_n^k - c$, or else $q$ would divide $p_n^k$. Since $q$ was arbitrary, we see that $\gcd(p_n^k - c, p_n - 1) = 1$, and so \[ \gcd(p_n^k-c,(p_n - 1)c) = \gcd(p_n^k-c,c) = \gcd(p_n^k,c). \]This greatest common divisor must be greater than $1$, and so $p_n$ must divide $c$. This completes the induction step and hence the proof. $\blacksquare$

djmathman wrote: Can someone please check this solution? I'm not sure if I ever invoke the condition that $c > 1$, so I'm concerned that this solution has a flaw that I'm not seeing. Thanks!

I only looked at it very quickly, but this looks right to me. We decided to only ask for $c>1$ because in many approaches it is a special case; we felt that the problem with $c>1$ was hard enough as it was, and didn't want to add additional complexity/casework to a problem that, in many solutions, already involved some substantial casework.

Actually if $c>1$ is removed, then $P(x)=x+1$ and $c=0$ creates a counterexample as then $x_n=n$ for all $n$ and $(x_n,n)=n$ for all positive integers $n$.

I saw it closely. @djmathman, when you claimed that $c$ can't have infinitely many primes divisors you assumed that it is nonzero. For $c=1$, it should work.

If $P(x) = x+1,$ then it follows that $x_n = n$ for all $n,$ so \[\gcd(x_n, n+c) = \gcd(n, n+c) = \gcd(n, c).\]Infinitely many $n$ satisfy $\gcd(n,c) = 1,$ so the problem is solved in this case. Now suppose $P(x) \neq x+1,$ and let $m$ be the least nonnegative integer for which $P(m) \neq m+1.$ (Such an integer exists because the nonzero polynomial $P(x) - (x+1)$ has only finitely many roots.) Then $P(k) = k+1$ for $0 \le k \le m-1,$ from which it follows that $x_k = k$ for $0 \le k \le m.$ First we dispose of the possibility that $P(m) = m-1.$ In this case, we have \[x_{m+1} = P(x_m) = P(m) = m-1 = x_{m-1},\]so the sequence $(x_n)$ eventually alternates between $m+1$ and $m-1.$ Thus, whenever $n+c$ is a prime greater than $m+1,$ we must have $\gcd(x_n, n+c) = 1$; there are infinitely many such $n,$ so the problem is solved. With that taken care of, assume $P(m) \neq m-1.$ Now we know $P(m) - m \neq \pm 1,$ so there is a prime $p$ dividing $P(m) - m.$ Then by induction, $x_n \equiv m \pmod p$ for all $n \ge m,$ since $x_m = m$ and \[x_n \equiv m \pmod p \implies x_{n+1} = P(x_n) \equiv P(m) \equiv m \pmod p.\]In addition, $P(m) - m \equiv P(m) \equiv P(0) = 1 \pmod m,$ so $\gcd(P(m) - m, m) = 1,$ which implies that $p \nmid m.$ Thus $p \nmid x_n$ for all $n \ge m.$ It follows that when $n \ge m$ and $n+c$ is a power of $p$ we have $\gcd(x_n, n+c) = 1,$ and there are infinitely many such values of $n.$

Wait so your problems haven't been graded yet? andersarnold123 wrote: This is my solution submitted on contest.I don't know if it is correct.

Can someone please check if this works? It seems too simple but I really can't see where I went wrong If $P(x) = x+1$ or $P(x) = 1$, the problem is trivial, so assume that $P(x)$ is something else. The problem is also trivial if the sequence of $x_i$ becomes periodic at some point, so assume that it is not periodic, meaning we can pick some $x_i$ with arbitrarily large absolute value. Since $P(x)-x$ is not constant, we have that for $k$ with $|k|$ arbitratrily large then $|P(k)-k|$ is arbitrarily large. Thus we can pick some $x_i$ with $|P(x_i)-x_i| \geq 2$, and pick some prime $p$ such that $p \mid P(x_i)-x_i$. However, that means $P(x_i) \equiv x_i \pmod{p}$, so for all $j \geq i$, we have $x_j \equiv x_i \pmod{p}$. Obviously $x_i \not\equiv 0 \pmod{p}$ or else $P(x_i) \equiv P(0) \equiv 1 \pmod{p}$. Then we can pick any $k$ with $p^k - c > i$ and have $\text{gcd} (x_{p^k-c}, p^k) = 1$, and since there's obviously infinitely many such $k$ we're done. Sorry for the bump by the way.

The key to this is that the sequence is periodic modulo every prime number,which is easy to check,and that the period contains exactly one number that is $0$ modulo $p$.Consider a prime number $p$.Let its period be $k$.Consider $n$ equals $p-c$ and $p^2-c$.This is the main idea.We can consider $p^a-c$.They should all have a common factor $k$,which is the period.Pick $p$ that is coprime with $c(c-1)$ and we get that numbers of the form $p^a-c$ can't have a common factor.From this,we have that at least one of the numbers of the form $p^a-c$ satisfay the condition.We have infinitely many primes that are coprime with $c(c-1)$,so we have infinitely many such $n$.

Severus wrote:

I believe this does not work if $P(1)=2$ , right?

Yes, right @above, my solution is indeed wrong

Here's a pretty weird/overkill proof: For moral reasons, we replace $P$ by $f$, and note that $x_n=f^n(0)$. FTSOC assume that there exists some integer $M$ such that $\text{gcd}(x_n,n+c)>1$ for all $n \geq M$. We start with the following well-known Lemmas:- LEMMA 1 For $k \geq 3$, there are no polynomials $f \in \mathbb{Z}[x]$ such that there exist integers $x_1,x_2, \dots ,x_k$ with $f(x_i)=x_{i-1}$ for all $1 \leq i \leq k$ (indices taken mod $k$). In other words, there are no solutions in integers to $f^k(x)=x$ for any $k \geq 3$. Proof of Lemma We can safely assume that all $x_i$'s are distinct for $1 \leq i \leq k$, else we will simply get an integer solution to $f^m(x)=x$ for some $m<k$. Note that $$x_i-x_{i-1} \mid f(x_i)-f(x_{i-1})=x_{i-1}-x_{i-2}$$Putting $i=k,k-1, \dots ,2$ in the above divisibility successively, we get $$x_k-x_{k-1} \mid x_{k-1}-x_{k-2} \mid \dots \mid x_1-x_k$$where we use $x_0=x_k$. But, for $i=1$, we have $f(x_1)-f(x_k) \mid f(x_k)-f(x_{k-1})$. So in fact we get that $$x_k-x_{k-1}=\pm(x_{k-1}-x_{k-2})=\pm(x_{k-2}-x_{k-3})= \dots =\pm(x_1-x_k)$$If $x_i-x_{i-1}=-(x_{i-1}-x_{i-2})$, then we get $x_i=x_{i-2}$ which can only happen if $k \leq 2$ (by our assumption that all $x_i$'s are distinct). So we must have $x_i-x_{i-1}=x_{i-1}-x_{i-2}$ for all $1 \leq i \leq k$. Writing this constant value as $C=x_i-x_{i-1}$, and adding it for $i=1,2, \dots ,k$, we get $kC=0$, or equivalently $C=0$, contrary to our assumption of distinct $a_i$'s. Thus, there are no such integers for $k \geq 3$. $\Box$ COROLLARY $x_i \neq 0$ for all $i \in \mathbb{N}$. Proof of Corollary Let $i$ be the minimal such index. If $i \geq 3$, then this contradicts Lemma 1. Also $i=1$ is not possible, as $f(0)=1$. So we must have $i=2$. Then $x_{2k-1}=1$ for all $k \in \mathbb{N}$, which contradicts the fact that there are only finitely many $n$ such that $\text{gcd}(x_n,n+c)=1$. So no such index $i$ exists. $\Box$ LEMMA 2 Let $d,n \in \mathbb{N}$ such that $d \mid n$. Then $x_d \mid x_n$. Proof of Lemma 2 Let $n=kd$. We prove this by induction on $k \geq 1$. The result is obvious for $k=1$. So assume that it is true for $k-1$. Then, using $x_d \mid x_{(k-1)d}$, we get $$f^d(0) \mid f^{(k-1)d}(f^d(0))-f^{(k-1)d}(0) \Rightarrow x_d \mid x_n-x_{(k-1)d} \Rightarrow x_d \mid x_n \text{ } \Box$$ LEMMA 3 $\text{gcd}(x_m,x_n)=x_{\text{gcd}(m,n)}$ for all positive integers $m,n$. Proof of Lemma 3 Note that by Lemma 2, we have $x_{\text{gcd}(m,n)} \mid \text{gcd}(x_m,x_n)$, and so it suffices to prove that $$\text{gcd}(x_m,x_n) \mid x_{\text{gcd}(m,n)}$$This is basically an application of Euclid's Division Algorithm. Indeed, suppose $m>n$ with $m=q_0n+r_0$ for some $0 \leq r_0<n$, and let $g=\text{gcd}(x_m,x_n)$. The result is already shown (in Lemma 2) for $r_0=0$. So assume $r_0>0$. Then $$g \mid f^n(0) \mid f^{m-n}(f^n(0))-f^{m-n}(0) \Rightarrow g \mid f^m(0)-f^{m-n}(0) \Rightarrow g \mid f^{m-n}(0)$$Continuing in this manner, we get $g \mid f^{r_0}(0)$. Now, we write $n=q_1r_0+r_1$, and again apply the same process. Then we either get $r_1=0$ or $g \mid f^{r_1}(0)$. Continue till we get to $r_k=0$ for some $k \in \mathbb{N}$ (which must happen by Euclid's Division Algorithm), in which case we will have $g \mid x_{r_{k-1}}$. Then $$\text{gcd}(m,n)=\text{gcd}(n,r_0)=\text{gcd}(r_0,r_1)= \dots =\text{gcd}(r_{k-2},r_{k-1})=r_{k-1}$$where the last equality follows from the fact that $r_k=0$. But we have already shown that $g \mid x_{r_{k-1}}=x_{\text{gcd}(m,n)}$, as desired. $\Box$ Return to the problem at hand. Note that, by Dirichlet's Theorem, there exist infinitely many primes of the form $a(c-1)+1$ for $a \in \mathbb{N}$. Choose one such prime $p$ greater than $M+c$. Then $\text{gcd}(x_{p^k-c},p^k)>1$ for all positive integers $k$. In particular, this means that $p \mid x_{p^2-c}$ and $p \mid x_{p-c}$. This gives that $p \mid \text{gcd}(x_{p-c},x_{p^2-c})$. By Lemma 3, we have $$\text{gcd}(x_{p-c},x_{p^2-c})=x_{\text{gcd}(p-c,p^2-c)} \Rightarrow p \mid x_{\text{gcd}(p-c,p^2-c)}$$Also, since $\text{gcd}(p,p-c)=1$, so we have $$\text{gcd}(p-c,p^2-c)=\text{gcd}(p-c,p^2-p)=\text{gcd}(p-c,p-1)=\text{gcd}(p-1,c-1)=c-1$$Thus, we have $p \mid x_{c-1}$ for all such primes. Since there are infinitely many such primes, so we must in fact have $x_{c-1}=0$. But, since $c>1$, so this contradicts Lemma 1. Hence, our initial assumption was wrong. $\blacksquare$

Severus wrote:

Can you tell me how does this solution cover the case$P(1)=2$ ?

@above, this solution is not correct and fails for the case you mentioned (which someone else pointed out in a previous post, and I acknowledged). I guess I'll make the edit in the original post.

pieater314159 wrote: Here's a solution that's very different in spirit:

Carl, why did you include $c > 1$ as a condition? Is this needed?

Suppose there's a polynomial $P\in \mathbb{Z}[x]$ making the statement fails. Since $P(0)=1,$ suppose $P(n)=n+1$ for $n=0,1,...k-1$ for $k\in\mathbb{N}$. If $\mid P(k)-k\mid\geq 2$ then there's a prime $p$ for which $p\mid P(k)-k$ so $P^m(k-1)$ all have remainder $k$ when divided by $p$ for all $m\in\mathbb{N}$ and since $P(k-1)=x_k$ and it's clear that $(k,p)=1$ we have $(x_{p^{\theta}-c},p^{\theta})=1$ for infinitely many $\theta$'s. Hence $P(k)=k-1\text{ or } k\text{ or }k+1$ If $P(k)=k$ then $P^L(k-1)=k$ for some big enough integers $L$ so we can choose integer $T$ with $(k,T+c)=1$ and $(x_T,T+c)=(k+1,T+c)=1$ for infinitely many $T$'s. If $P(k)=k-1$ then for big enough integers $S, x_S=k-1$ if $2\mid S+k+1$ and $x_S=k$ if $2\mid S+k$. If $c$ is odd then $(x_{(k-1)^R-c},(k-1)^R)=(k,(k-1)^R)=1$ for infinitely many big enough integers $R$'s. if $c$ is even but $k$ is odd then $(x_{(k-1)^G-c+1},(k-1)^G+1)=1$ for infinitely many $G's$. if both $c,k$ are even, pick a $j\in\mathbb{N}$ s.t. $(j,k-1)=1$ then we have $(x_{(k-1)^H+j-c},(k-1)^H+j)=(k-1,j)=1$ for infinitely many large enough integers $H$'s. Thus $P(x)=x+1$ which is obviously wrong.

We consider two cases: Case 1: $P(x) - x$ is constant. Then, $\deg(P) \leq 1$ and hence we can write $P(x) = mx + 1$ for some integer $m \in \{0, 1\}$. If $m = 0$, then $\gcd(P^n(0), n+c) = 1$ always, and otherwise, we have by Euclidean Algorithm that $\gcd(P^n(0), n+c) = \gcd(n, n+c) = \gcd(n, c)$ which can clearly achieve $1$ infinitely many times as $c$ is fixed. Case 2: $P(x) - x$ is not constant. Denote $Q(x) = P(x) - x$. Then, $Q$ has degree $\geq 1$ (WLOG positive leading coefficient) and thus, for arbitrarily large $k$, larger than any of the roots of $Q$, that $Q(k)$ is also large (and increasing to $\infty$). For such large $k$, note that if we take a prime $p \mid Q(k)$, then\[P(k) \equiv k \pmod p \implies P^r(k) \equiv P^{r-1}(k) \pmod p \implies P^r(k) \equiv P^{r-1}(k) \equiv \ldots \equiv k \pmod p\]for any positive integer $r$. Thus, if the sequence $\{x_i\}_{i = 0}^{\infty}$ was unbounded, then we could take $k = x_i$ for large enough $x_i$, so that\[P^r(x_i) = x_{i+r} \equiv x_i \pmod p\]for any positive integer $k$. Furthermore, $p \nmid x_i$ since by definition, note $\gcd(P(x_i) - x_i, x_i) = 1$ because $P(x_i) \equiv P(0) = 1 \pmod {x_i}$. Thus, $x_{i+r} \equiv x_i \not \equiv 0 \pmod p$, and for every $n \geq i$ of the form $p^e - c$, indeed, we have that $\gcd(x_n, p^e) = 1$, of which there are clearly infinitely many $n$. If $x_2 = 1$, then the entire sequence is $1$, at which point we clearly are finished. Else, if the sequence $\{x_i\}_{i = 0}^{\infty}$ were not unbounded, then it would be eventually periodic, at which point the problem becomes clear, so we may solve the problem for if the sequence were unbounded with the solution presented in the above section.

Hm, not sure if this works. Let $p$ be a prime. We will consider the sequence $x_i$ entirely mod $p$. If there exists no $i > 0$ such that $x_i = 0$, we are done by setting $n = p^k - c$ for all sufficiently large $k$. Otherwise, let $i$ be the smallest such index. Clearly the sequence is periodic with period dividing $i$. Moreover if the period was less than $i$ there would be an occurrence of $0$ between $x_0$ and $x_i$, contradicting the minimality of $i$ so the sequence is periodic with period $i$. In particular, for any $k$, $x_k = 0$ iff $i | k$. Now, for any $k$, $\text{gcd}(p^k - c, p^{k+1} - c) = \text{gcd}(p^k - c, (p-1)c)$. Since $p - 1 | p^k - 1$, $\text{gcd}(p^k-c,p-1) = \text{gcd}(c-1, p-1)$ so if we choose $p$ such that $\text{gcd}(p-1,c-1) = \text{gcd}(p,c) = 1$ which exists by Dirichlet's, $p^k - c$ will be relatively prime to $p^{k+1} - c$ for all $k$. In particular, $p^k - c$ will not be a multiple of $i$ for infinitely many (sufficiently large) $k$, so we are done again by setting $n = p^k - c$ for all such $k$.

Very Fun Problem First, define $P^n(0)=x_n$ for all nonnegative integers $n$. Assume for the sake of contradiction that there are only finitely many $n$ for which $\gcd(P^n(0),n+c)=1$. So there exist positive integers $M$ such that for all $n>M$, we have $\gcd(P^n(0),n+c)\neq 1$. Plug $n\mapsto p^k-c$ where $p>c+M$ is sufficiently large prime. Then $\gcd(P^{p^k-c}(0),p^k)\neq 1$ so $p\mid P^{p^k-c}(0)$ for all $p>c+m$ and positive integers $k$. But we’ll really be focusing on $p\mid P^{p-c}(0),P^{p^2-c}(0)$. If $P^n(0)=0$ for some $n>0$ then the sequence $P^i(0)$ is periodic with period $n$. Hence $P^{nk+1}(0)=P(0)=1$. This give a clear contradiction since $\gcd(P^{nk+1}(0),nk+1+c)=1$ for all $k$. Suppose that $P^i(0)\neq 0$ for all $i>0$. Claim 1: If $p\mid P^a(0),P^b(0)$ then $p\mid P^{\gcd(a,b)}(0)$. Proof. WLOG $a\geq b$. Note that $$p\mid P^b(0)-0\mid P^{a-b}(P^b(0))-P^{a-b}(0)\implies p\mid P^{a-b}(0).$$We do this repeatedly like the Euclidean’s algorithm to get that $p\mid P^{\gcd(a,b)}(0)$. We’ll use the claim 1. Note that \begin{align*} \gcd(p-c,p^2-c)&=\gcd(p-c,p^2-p) \\ &\stackrel{p>c}{=}\gcd(p-c,p-1) \\ &=\gcd(c-1,p-1). \end{align*}Thus, we have $p\mid P^{\gcd(c-1,p-1)}(0)$. Claim 2: If $a\mid b$ then $P^a(0)\mid P^b(0)$. Proof. We'll prove by induction on $n$ that $P^a(0)\mid P^{na}(0)$. There is nothing to prove in the base case $n=1$. Suppose that $P^a(0)\mid P^{(n-1)a}(0)$. $$P^a(0)-0\mid P^{(n-1)a}(P^a(0))-P^{(n-1)a}(0)\implies P^a(0)\mid P^{na}(0)$$ Since $c>1$, we have $\gcd(c-1,p-1)> 0$ and so $\gcd(c-1,p-1)\mid c-1$. Therefore, by claim 2, we have $p\mid P^{\gcd(c-1,p-1)}(0)\mid P^{c-1}(0)$ for all $p>c+M$ forcing $P^{c-1}(0)$ to be $0$ which contradict $P^i(0)\neq 0$ for all $i>0$, and we're done. Remark. Because of claim 1 and 2, we also get that $\gcd(P^a(0),P^b(0))=P^{\gcd(a,b)}(0))$.

Suppose otherwise. Let $p$ be an arbitrary prime and consider the "arrows graph" on $\mathbb{Z}/p\mathbb{Z}$ where $x$ points to $P(x)$. If $p$ is large enough, then for every positive integer $k$ we should have $\gcd(x_{p^k-c},p^k)>1 \implies p \mid x_{p^k-c}$. Hence the length of the cycle in the graph containing $0$ must divide $p^k-c$ for every $k$. Thus, it must divide $(p^{k+1}-c)-(p^k-c)=p^k(p-1)$, and since $p$ is large so that $p \nmid c$, this means that it must divide $p-1$, so it must divide $(p-1)-(p-c)=c-1$. Thus, for any large enough $p$, we have $p \mid x_{c-1}$, hence for any $m \geq 1$ we have $x_{m(c-1)}=0 \implies x_{m(c-1)+1}=1$, so $\gcd(x_{m(c-1)+1},m(c-1)+1+c)=1$. $\blacksquare$

Suppose for contradiction that for sufficiently large $n$, we have $\gcd(x_n,n+c)>1$. Let $p>c$ be a sufficiently large prime. Let $q$ be such that $q\mid p+c$ and $q\mid x_p$. Note that since $p < p+c < 2p$, it is impossible for $q\geq p$. Hence, $q < p$. Consider the sequence $\{0,P(0),P(P(0)),\ldots,P^n(0),\ldots\}\pmod{q}$. We have $P^p(0)\equiv0\pmod{q}$, which means that the sequence is periodic with period $r$, and $r\mid p$. Hence, $r=1$ or $r=p$. However $r=1$ is impossible as $1=P(0)\ne0\pmod{q}$. So, $r=p$. But this means that $\{0,P(0),P(P(0)),\ldots,P^p(0)\}$ is a complete residue set $\pmod{q}$ with no repetitions, which is impossible as $p>q$, and hence repititions must occur. This gives us the required contradiction. $\blacksquare$

Claim: There exists a prime $p$ such that $\gcd (p,c) = 1$ and $\gcd( p-1, c-1) = 1$. Proof: If $c$ is odd, pick $p=2$. Otherwise, if $c$ is even, by Dirichlet's theorem, there exist infinitely many primes congruent to $2$ mod $c-1$, all of which satisfy the second GCD condition – a sufficiently large prime will satisfy the first one as well. Fix this value of $p$. Define $a(i) = p^i - c$. Due to our selection of $p$, every value in $a(i)$ is coprime to both $p$ and $p-1$, so $\gcd (a(i), a(i+1)) = 1$ for all $i \neq j$. Claim: The values $x_{a(i)}$ and $x_{a(i+1)}$ are not both multiples of $p$. Proof: Suppose FTSOC that $i \neq j$ are such that $x_{a(i)}$ and $x_{a(i+1)}$ are both multiples of $p$. Then, combining $x_0 = 0$ and the fact that $x$ is eventually periodic mod $p$, it follows that $x$ is completely periodic with a period that divides $\gcd (a(i), a(i+1))$. However, since this GCD is $1$, this implies that $x_i$ is constant, contradicting the fact that $x_1 = 1$. So, for each $i$, selecting either $n = x_{a(i)}$ or $n=x_{a(i+1)}$ will satisfy $\gcd (x_n, n+c ) = 1$.