SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Suppose that $P,Q\in \mathbb{Z}[x]$ satisfy the given requirement. Step by step we will draw some conclusions.

Step 1. $\mathrm{deg}P\ge 1,\mathrm{deg}Q\ge 1$. Suppose, on the contrary, that one of $P,Q$ were a constant polynomial $c$. 1. If $P(x)=c(\forall x\in \mathbb{Z})$, then $$x_n\in \{2016,c,Q(c)\}\forall n\ge 0.$$ 2. If $Q(x)=c(\forall x\in \mathbb{Z})$, then $$x_n\in \{2016,P(2016),c,P(c)\}\forall n\ge 0.$$ In both cases, the requirement "every positive integer is a divisor of a certain nonzero term of the sequence ${\left(x_n\right)}_{n=0}^{\infty }$" couldn't be satisfied. Hence, $\mathrm{deg}P\ge 1,\mathrm{deg}Q\ge 1$.

Step 2. $\mathrm{deg}Q=1$. Suppose, on the contrary, that $\mathrm{deg}Q>1$. By Step 1, $\mathrm{deg}P\ge 1$, so there exist positive numbers $M$ and $k\ge 1$ such that $k|P(x)|\ge |x|$ for all $x\in \mathbb{Z}$ with $|x|\ge M$. In particular, ${\lim }_{|x|\to \infty }|P(x)|=\infty$. But $\mathrm{deg}Q>1$, which implies that $$\underset{|x|\to \infty }{\lim }\frac{|Q(x)|}{|x|}=\infty ;$$ therefore, if $N\in (M,\infty )$ is chosen large enough, then we have: $$|Q(x)|>|x|$$ and $$|Q(P(x))|>2k|P(x)|=k|P(x)|+k|P(x)|\ge k|P(x)|+|x|$$ when $|x|\ge N$. Now, in accordance with the given requirement, ${\lim }_{n\to \infty }{\max }_{0\le \ell \le 2n}\left|x_{\ell }\right|=\infty$. Further, for large $n$, let $0\le i=i(n)\le 2n$ be an index such that $$\left|x_i\right|=\underset{0\le \ell \le 2n}{\max }\left|x_{\ell }\right|>N.$$ If $i$ were odd, say $i=2j-1$, then we would get $$\left|x_{2j}\right|=\left|Q\left(x_{2j-1}\right)\right|>\left|x_{2j-1}\right|=\underset{0\le \ell \le 2n}{\max }\left|x_{\ell }\right|,$$ a contradiction (since $2j\le 2n$ ). So, $i$ should be even (when $n$ is large enough), say $i=2j$. For such a $j$, take $m=\left|x_{2j+2}-x_{2j}\right|$. Then $$m=\left|Q\left(P\left(x_{2j}\right)\right)-x_{2j}\right|\ge \left|Q\left(P\left(x_{2j}\right)\right)\right|-\left|x_{2j}\right|>k\left|P\left(x_{2j}\right)\right|\ge \left|x_{2j}\right|$$ and $m>k\left|P\left(x_{2j}\right)\right|\ge \left|P\left(x_{2j}\right)\right|=\left|x_{2j+1}\right|$. Therefore, among the first $2j+2$ terms $x_0,x_1,\dots ,x_{2j},x_{2j+1}$, there do not exist any term which is nonzero and which is divisible by $m$. It should also be noted here that $x_{2j}{x}_{2j+1}\ne 0$ (since $\left|x_{2j+1}\right|=\left|P\left(x_{2j}\right)\right|\ge \frac{|x_{2j}|}{k}>\frac{N}{k}>0$ ). Hence, neither $x_{2j}$ nor $x_{2j+1}$ is divisible by $m$. On the other hand, $$\left(x_{2\ell +2}-x_{2\ell }\right)\mid \left(Q\left(P\left(x_{2\ell +2}\right)\right)-Q\left(P\left(x_{2\ell }\right)\right)\right)=x_{2\ell +4}-x_{2\ell +2}$$ and $$\left(x_{2\ell +2}-x_{2\ell }\right)\mid \left(P\left(x_{2\ell +2}\right)-P\left(x_{2\ell }\right)\right)=x_{2\ell +3}-x_{2\ell +1}.$$ Thus, if $\ell \ge j$, then $x_{2\ell +2}-x_{2\ell }$ and $x_{2\ell +3}-x_{2\ell +1}$ are both divisible by $m=\left|x_{2j+2}-x_{2j}\right|$. But, as we have shown above, neither $x_{2j}$ nor $x_{2j+1}$ is divisible by $m$. It follows that neither $x_{2\ell +2}$ nor $x_{2\ell +3}$ is divisible by $m$ when $\ell \ge j$. Therefore, $m$ could not be a divisor of any nonzero term of the sequence ${\left(x_n\right)}_{n=0}^{\infty }$, a contradiction again! So, $\mathrm{deg}Q=1$.

Step 3. $\mathrm{deg}P=1$. The proof is similar to that in Step 2.

Step 4. Now $P(x)=ax+b,Q(x)=cx+d$ with $a,b,c,d\in \mathbb{Z}$ and $ab\ne 0$. We will prove that $ac=1$. By definition, $$\{\begin{array}{l}{x}_{2n+1}=a{x}_{2n}+b\\ x_{2n+2}=c{x}_{2n+1}+d\end{array}\forall n\ge 0.$$ Hence, $x_{2n+2}=ac{x}_{2n}+bc+d$ and $x_{2n+3}=ac{x}_{2n+1}+ad+b$ for all $n\ge 0$. These 2 sub-sequences share a common recurrence relation of the form $y_{n+1}=r{y}_n+s$ with $s\in \mathbb{Z},r=ac$. Suppose, on the contrary, that $r\ne 1$. Then $$y_n=r^n{y}_0+s\frac{r^n-1}{r-1}\forall n\ge 0.$$ If $r=-1$, then $y_n\in \left\{y_0,-y_0+s\right\}(\forall n)$; therefore, the given requirement could not be satisfied. So, $|r|>1$. The requirement implies that one of the above-mentioned 2 sub-sequences has the following property: for each $q\in {\mathbb{N}}_0$ there is an $n=n(q)\in {\mathbb{N}}_0$ such that $r^q\mid y_n\ne 0$. Of course, $n\to \infty$ as $q\to \infty$. Moreover, $$r^{\min \{q,n\}}|\left(y_n-r^n{y}_0\right)=s\frac{r^n-1}{r-1}.$$ Since $\gcd \left(r,\frac{r^n-1}{r-1}\right)=1$, it follows that $r^{\min \{q,n\}}\mid s$ (for all $q$ ). But $|r|>1$ and $\min \{q,n\}\to \infty$ as $q\to \infty$, we see that $s=0$. Hence, $y_n=r^n{y}_0(\forall n)$, and therefore, the requirement could not be satisfied. This contradiction shows that $r=ac=1$.

Step 5. Finally, $P(x)=\pm x+b,Q(x)=\pm x+d$ where $b,d\in \mathbb{Z}$ are to be found. We have to consider two cases: - $P(x)=x+b$ and $Q(x)=x+d$ with $b,d\in \mathbb{Z}$. In this case, by induction, we can show that $$x_{2n}=2016+n(b+d)\text{ and }{x}_{2n+1}=2016+b+n(b+d)\forall n\ge 0.$$ So, a necessity condition for the requirement to be satisfied is $b+d\ne 0$. Under this condition, the requirement says that for each $m\in \mathbb{N}$ one of the linear congruences $$(b+d)x\equiv -2016(\mathrm{mod}m),(b+d)x\equiv -(2016+b)(\mathrm{mod}m)$$ has (infinitely many) solutions $x=n$ in ${\mathbb{N}}_0$. Equivalently, $\gcd (b+d,m)\mid 2016$ or $\gcd (b+d,m)\mid (2016+b)$ for each $m\in \mathbb{N}$. It suffices to consider $m=|b+d|$ and obtain the condition: $$(b+d)\mid 2016\text{ or }(b+d)\mid (2016+b),\text{ where }b+d\ne 0$$ - $P(x)=-x+b$ and $Q(x)=-x+d$ with $b,d\in \mathbb{Z}$. In almost the same manner, we see that the requirement is satisfied if and only if $$(b-d)\mid 2016\text{ or }(b-d)\mid (-2016+b),\text{ where }b-d\ne 0.$$

Remark. We are going to give here another proof of the conclusions in Steps 2-3 (the proof of that in Step 1 and Steps 4-5 will be the same). We need the following lemma.

Lemma. Let $a\in \mathbb{Z}$ and $T\in \mathbb{Z}[x]$ be given. A sequence ( $y_n$ ) is defined as $$y_0=a,y_{n+1}=T\left(y_n\right)\forall n\ge 0$$ Suppose that each positive integer $m$ is a divisor of some nonzero term of $\left(y_n\right)$. Then $\mathrm{deg}T=1$.

Proof. It is easy to check that any constant polynomial $T$ does not satisfy the given condition. We suppose on the contrary that $\mathrm{deg}T>1$. Then there exists $c>0$ such that $|T(x)|>2|x|$ whenever $|x|>c$. By assumption, ${\lim }_{m\to \infty }{\max }_{0\le \ell \le m}\left|y_{\ell }\right|=\infty$. Further, let $0\le n=n(m)\le m$ be the smallest index such that $\left|y_n\right|={\max }_{0\le \ell \le m}\left|y_{\ell }\right|$. Then $n\to \infty$ as $m\to \infty$, and $\left|y_n\right|>\left|y_i\right|$ for all $0\le i<n$. Hence, we can choose an $N\in \mathbb{N}$ such that $\left|y_N\right|>\max \left\{c,\left|y_0\right|,\left|y_1\right|,\dots ,\left|y_{N-1}\right|\right\}$. In particular, this implies that $$\left|y_{N+1}\right|=\left|T\left(y_N\right)\right|>2\left|y_N\right|.$$ Set $m=\left|y_{N+1}-y_N\right|$. Then $$m\ge \left|y_{N+1}\right|-\left|y_N\right|>\left|y_N\right|>\max \left\{\left|y_0\right|,\left|y_1\right|,\dots ,\left|y_{N-1}\right|\right\}.$$ Therefore, $y_N$ is not divisible by $m$. Moreover, $m$ is not a divisor of any nonzero term among $y_0,y_1,\dots ,y_{N-1}$. On the other hand, $y_{n+1}-y_n$ is divisible by $y_n-y_{n-1}$ for all $n\ge 1$. So, $y_{n+1}-y_n$ is divisible by $m=\left|y_{N+1}-y_N\right|$ for all $n\ge N$. It follows that $$y_n-y_N=\left(y_n-y_{n-1}\right)+\left(y_{n-1}-y_{n-2}\right)+\dots +\left(y_{N+1}-y_N\right)$$ is divisible by $m$ for all $n>N$. But $y_N$ is not divisible by $m$, so $y_n$ is not divisible by $m$ for all $n>N$, which is a contradiction. This completes the proof of the lemma.

We are now in a position to prove the conclusions of Steps 2-3. Let $H(x)=P(Q(x))$ and $K(x)=Q(P(x))$. Suppose, on the contrary, that either $\mathrm{deg}P\ge 2$ or $\mathrm{deg}Q\ge 2$. Then $\mathrm{deg}H\ge 2$ and $\mathrm{deg}K\ge 2$ (since, by Step $1,\mathrm{deg}P\ge 1,\mathrm{deg}Q\ge 1$ ). Consider the sub-sequence $\left(x_0,x_2,x_4,\dots \right),x_{2(n+1)}=K\left(x_{2n}\right)$ for all $n\ge 0$. Because $\mathrm{deg}K\ge 2$, the sequence $\left(y_n\right)=\left(x_{2n}\right)$ cannot satisfy the condition given in the lemma. Thus, there exists a positive integer $m$ such that none of $m,2m,3m,\dots$ can be a divisor of a certain nonzero term $x_{2n}$. This implies that for each $k\in \mathbb{N}$ there exists a nonzero term $x_{2n_k+1}$ divisible by $km$. Therefore, the sub-sequence $$\left(x_1,x_3,x_5,\dots \right),x_{2n+3}=H\left(x_{2n+1}\right)$$ (for all $n\ge 0$ ), satisfies the condition given in the lemma. According to this lemma, $\mathrm{deg}H=1$, a contradiction. This contradiction shows that $\mathrm{deg}P=1,\mathrm{deg}Q=1$.