55th IMO Team Selection Test

We have $x{f}^2(x)+f(x)=(x^3-x)g^2(x)\iff [2xf(x)+1{]}^2=(x^2-1)[2xg(x){]}^2+1$. We will now find all pairs $(p,q)$ of integer-coefficient polynomials such that $p^2(x)=(x^2-1)q^2(x)+1$. Let $(p,q)$ be one such pair such that the degree of $q$ is $k\ge 1$. We can assume, without loss of generality, that $p$ and $q$ have positive leading coefficients. Let $P_0=$

$p$ and $Q_0=q$ and let $P_1(x)=xp(x)-(x^2-1)q(x)$ and $Q_1(x)=-p(x)+xq(x)$. It is easy to show that $P_1$ and $Q_1$ also satisfy the given equation and that the degree of $Q_1$ is strictly less than the degree of $Q_0$. (One way to come up with this construction is as follows. The equation on $p$ and $q$ can be rewritten as $1=(p(x)-q(x)\sqrt{x^2-1})(p(x)+q(x)\sqrt{x^2-1})$. Also, one of its solutions is given by $(p,q)=(x,1)$, i.e. $1=(x-\sqrt{x^2-1})(x+\sqrt{x^2-1})$. Multiplying the last two equations then gives us exactly $1=(P_1(x)-Q_1(x)\sqrt{x^2-1})(P_1(x)+Q_1(x)\sqrt{x^2-1})$.) Continuing this process, we will eventually arrive at a solution $(P_s,Q_s)$ such that $Q_s$ is constant. There are, however, only two solutions of this kind: $(x,1)$ and $(1,0)$. Since applying the operation to the former yields the latter, we can, without loss of generality, assume that $(P_s,Q_s)=(1,0)$. It follows that all solution pairs $(p,q)$ are given by the sequence determined by the initial condition $(p_0,q_0)=(1,0)$ and the recurrence relation $(p_{i+1},q_{i+1})=(x{p}_i(x)+(x^2-1)q_i(x),p_i(x)+x{q}_i(x))$. (Or, more precisely, this recurrence yields those solutions in which the leading coefficients of $p$ and $q$ are positive.) A member of that sequence corresponds to a solution of the original equation exactly when $p(x)$ is congruent to $1(\mathrm{mod}2x)$ and $q(x)$ is divisible by $2x$. Since the first five members of the sequence are $(1,0)$, $(x,1)$, $(2x^2-1,2x)$, $(4x^3-3x,4x^2-1)$, and $(8x^4-8x^2+1,8x^3-4x)$ and $(p_4(x),q_4(x))\equiv (1,0)(\mathrm{mod}2x)$, the sequence is periodic with period $4(\mathrm{mod}2x)$ and exactly the members $(p_i,q_i)$ such that $i$ is a multiple of $4$ yield a solution. Therefore, the necessary values of $n$ are the numbers $4k+3$ for $k\ge 0$.