Putnam 2007, Problem B-4

Let $n$ be a positive integer. Find the number of pairs $P,Q$ of polynomials with real coefficients such that
$$(P(X))^2 + (Q(X))^2 = X^{2n} + 1$$
and $\deg P > \deg Q$.

Solution:
The number of pairs is $2^{n+1}$. The degree condition forces $P$ to have degree $n$ and leading coefficient $\pm 1$; we may count pairs in which $P$ has leading coefficient 1 as long as we multiply by 2 afterward.

Factor both sides:
$$(P(X) + Q(X)i)(P(X) - Q(X)i) = \prod_{j=0}^{n-1}(X - \exp(2\pi i(2j+1)/(4n))) \cdot \prod_{j=0}^{n-1}(X + \exp(2\pi i(2j+1)/(4n))).$$

Then each choice of $P, Q$ corresponds to equating $P(X) + Q(X)i$ with the product of some $n$ factors on the right, in which we choose exactly of the two factors for each $j = 0, \ldots, n-1$. (We must take exactly $n$ factors because as a polynomial in $X$ with complex coefficients, $P(X) + Q(X)i$ has degree exactly $n$. We must choose one for each $j$ to ensure that $P(X) + Q(X)i$ and $P(X) - Q(X)i$ are complex conjugates, so that $P, Q$ have real coefficients.) Thus there are $2^n$ such pairs; multiplying by 2 to allow $P$ to have leading coefficient $-1$ yields the desired result.

**Remark:** If we allow $P$ and $Q$ to have complex coefficients but still require $\deg(P) > \deg(Q)$, then the number of pairs increases to $2\binom{2n}{n}$, as we may choose any $n$ of the $2n$ factors of $X^{2n} + 1$ to use to form $P(X) + Q(X)i$.