Team selection tests

By fixing $x\in \mathbb{Z}$, we obtain that $Q(x{)}^{2n}-1$ is a multiple of $P(x{)}^{2n}-1$ for all positive integer $n$. We now prove the following lemma.

Lemma. If $a$ and $b$ are two integers larger than $1$ such that $a^n-1\mid b^n-1$ for all positive integer $n$ then $b=a^k$ for some positive integer $k$.

Proof. (adapted from Andreescu, T., Dospinescu, G, Problems from the Book.) Let $x_n=\frac{b^{n-1}}{a^{n-1}}$ and consider the sequence $(x_n^{(i)}{)}_{n>0}$ indexed by $i>0$ defined by the formulas $$x_n^{(i+1)}=b{x}_n^{(i)}-a^i{x}_{n+1}^{(i)},x_n^{(1)}=x_n.$$ We can show by induction that $x_n^{(i)}$ can be written as $$\frac{c_i^{(i)}{b}^n+c_{i-1}^{(i)}{a}^{(i-1)n}+\cdots +c_1^{(i)}{a}^n+c_0^{(i)}}{(a^n+i-1-a)\dots (a^n-1)}.$$ Thus, for the index $i$ such that $a^i>b$, we obtain that ${\lim }_{n\to \infty }{x}_n^{(i)}=0$. However, by the definition, $x_n^{(1)}\in \mathbb{Z}$ for all $n$, thus all the terms $x_n^{(i)}$ are integers, which means $x_n^{(i)}=0$ for $n$ sufficiently large. We suppose that $j$ is the minimal index satisfying $x_n^{(j)}=0$ for all $n\ge M_j$. We have $$x_n^{(j)}=0⟹b{x}_n^{(j-1)}=a^j{x}_{n+1}^{(j-1)}$$ which concludes by induction that $$x_n^{(j-1)}={\left(\frac{b}{a^j}\right)}^{n-M}{x}_M^{(j-1)}.$$ By setting $\frac{b}{a^j}=c>0$, we obtain that $c^{M-n}\cdot x_n^{(j-1)}\in \mathbb{Z}$ for all $M>n$, which means $c\in \mathbb{Z}$ or $x_n^{(j-1)}=0$. The latter cannot hold since it follows that $x_M^{(j-1)}=0$ for all $M\ge n$, thus contradicts the minimality of $j$. In conclusion, $c\in \mathbb{Z}$ thus $a$ is a divisor of $b$. Now, write $b=ca$ for $c\in {\mathbb{Z}}_{>0}$, we have $$a^n-1\mid (ac{)}^n-1⟹a^n-1\mid c^n-1$$ thus we can prove similarly that $a\mid c$ or $c=1$. Repeating this process, we obtain $b=a^k$ for some $k$.

Back to the problem, since $(Q(x{)}^2{)}^n-1$ is divisible by $(P(x{)}^2{)}^n-1$ for all pairs $(x,n)\in \mathbb{Z}\times {\mathbb{Z}}_{>0}$. If $\mathrm{deg}P>0$ and $\mathrm{deg}Q>0$, there exists an integer $x_0$ such that for all $x>x_0$, one has $|P(x)|,|Q(x)|>1$. The lemma concludes that for each $x>x_0$, there exists an integer $k_x$ such that $$|Q(x)|=|P(x){|}^{k_x}.$$ On the other hand, if we write $\frac{\mathrm{deg}Q}{\mathrm{deg}P}=k$ then for all $\epsilon >0$, we have $$\underset{n\to \infty }{\lim }\frac{|P(x){|}^{k-\epsilon }}{|Q(x)|}=0,\underset{n\to \infty }{\lim }\frac{|P(x){|}^{k+\epsilon }}{|Q(x)|}=+\infty$$ thus $k=k_x$ for all sufficiently large $x$, which means $|Q|$ is a power of $|P|$. It remains to consider the case $\mathrm{deg}P<1$ or $\mathrm{deg}Q<1$.

If $\mathrm{deg}Q<1$ and $\mathrm{deg}P>1$, we always have $\mathrm{deg}{Q}^{2n}-1<\mathrm{deg}(P^{2n}-1)$ thus $Q^{2n}=1$, which means $Q(x)\equiv 1$ or $-1$.

If $\mathrm{deg}P<1$, write $P(x)=p$. If $|p|=1$, we have $Q^{2n}=1$ thus $Q(x)\equiv 1$ or $-1$. Otherwise, we obtain $Q(x{)}^{2n}-1$ is a multiple of $p^{2n}-1$ for all $n$, thus $|Q(x)|=p^{k_x}$ for some $k_x$. By Schur's lemma, if $\mathrm{deg}Q>0$, the sequence $(Q(n){)}_{n\ge 0}$ has infinitely many prime divisors, which is a contradiction because almost all the prime divisors of this sequence are divisors of $p$. In this case, we conclude that $\mathrm{deg}Q=0$ and $|Q(x)|=p^k$ for some fixed positive integer $k$.

So the polynomials $Q(x)$ satisfying the problem are: $$Q(x)=\pm P(x{)}^k$$ for some positive integer $k$, or $Q(x)\equiv \pm 1$.