IMO Team Selection Test

We have $xf^2(x) + f(x) = (x^3 - x)g^2(x) \Leftrightarrow [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}) = (xp_i(x) + (x^2-1)q_i(x), p_i(x) + xq_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 \pmod{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) \pmod{2x}$, the sequence is periodic with period $4 \pmod{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$.