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)}, \quad 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} + \dots + 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 \implies 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 = c a$ for $c \in \mathbb{Z}_{>0}$, we have
$$a^n - 1 \mid (a c)^n - 1 \implies 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 $\deg P > 0$ and $\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{\deg Q}{\deg P} = k$ then for all $\varepsilon > 0$, we have
$$\lim_{n \to \infty} \frac{|P(x)|^{k-\varepsilon}}{|Q(x)|} = 0, \quad \lim_{n \to \infty} \frac{|P(x)|^{k+\varepsilon}}{|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 $\deg P < 1$ or $\deg Q < 1$.

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

* If $\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 $\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 $\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$.