IMO 1996 SL A6

Origin: IRE | Category: Algebra

Problem

Let $n$ be an even positive integer. Prove that there exists a positive integer $k$ such that

$$k=f(x)(x+1)^n+g(x)(x^n+1)$$

for some polynomials $f(x)$, $g(x)$ having integer coefficients. If $k_0$ denotes the least such $k$, determine $k_0$ as a function of $n$.

$A6'$ Let $n$ be an even positive integer. Prove that there exists a positive integer $k$ such that

$$k=f(x)(x+1)^n+g(x)(x^n+1)$$

for some polynomials $f(x)$, $g(x)$ having integer coefficients. If $k_0$ denotes the least such $k$, show that $k_0=2^q$, where $q$ is the odd integer determined by

$$n=q2^r,\qquad r\in\mathbb{N}.$$

$A6''$ Prove that for each positive integer $n$, there exist polynomials $f(x)$, $g(x)$ having integer coefficients such that

$$f(x)(x+1)^{2n}+g(x)(x^{2n}+1)=2.$$

Solution

Let $f(x)$, $g(x)$ be polynomials with integer coefficients such that

$$f(x)(x+1)^n+g(x)(x^n+1)=k_0. \tag{*}$$

Write

$$n=2^rm$$

for $m$ odd and note that

$$x^n+1=(x^{2^r}+1)B(x),$$

where

$$B(x)=x^{2^r(m-1)}-x^{2^r(m-2)}+\cdots-x^{2^r}+1.$$

Moreover,

$$B(-1)=1;$$

hence

$$B(x)-1=(x+1)c(x),$$

and thus

$$R(x)B(x)+1=(B(x)-1)^n=(x+1)^nc(x)^n \tag{1}$$

for some polynomials $c(x)$ and $R(x)$.

The zeros of the polynomial $x^{2^r}+1$ are $\omega_j$, with

$$\omega_1=\cos\frac{\pi}{2^r}+i\sin\frac{\pi}{2^r},$$

and

$$\omega_j=\omega_1^{2j-1}$$

for $1\leq j\leq 2^r$. We have

$$(\omega_1+1)(\omega_2+1)\cdots(\omega_{2^r}+1)=2. \tag{2}$$

From $(*)$ we also get

$$f(\omega_j)(\omega_j+1)^n=k_0$$

for $j=1,2,\ldots,2^r$. Since

$$A=f(\omega_1)f(\omega_2)\cdots f(\omega_{2^r})$$

is a symmetric polynomial in $\omega_1,\ldots,\omega_{2^r}$ with integer coefficients, $A$ is an integer. Consequently, taking the product over

$$j=1,2,\ldots,2^r$$

and using $(2)$ we deduce that

$$2^nA=k_0^{2^r}$$

is divisible by

$$2^n=2^{2^rm}.$$

Hence

$$2^m\mid k_0.$$

Furthermore, since

$$\omega_j+1=(\omega_1+1)p_j(\omega_1)$$

for some polynomial $p_j$ with integer coefficients, $(2)$ gives

$$(\omega_1+1)^{2^r}p(\omega_1)=2,$$

where

$$p(x)=p_2(x)\cdots p_{2^r}(x)$$

has integer coefficients. But then the polynomial

$$(x+1)^{2^r}p(x)-2$$

has a zero $x=\omega_1$, so it is divisible by its minimal polynomial

$$x^{2^r}+1.$$

Therefore

$$(x+1)^{2^r}p(x)=2+(x^{2^r}+1)q(x) \tag{3}$$

for some polynomial $q(x)$.

Raising $(3)$ to the $m$th power we get

$$(x+1)^np(x)^n=2^m+(x^{2^r}+1)Q(x)$$

for some polynomial $Q(x)$ with integer coefficients. Now using $(1)$ we obtain

$$(x+1)^nc(x)^n(x^{2^r}+1)Q(x) =(x^{2^r}+1)Q(x)+(x^{2^r}+1)Q(x)B(x)R(x)$$

and therefore

$$(x+1)^np(x)^n-2^m+(x^n+1)Q(x)R(x).$$

Therefore

$$(x+1)^nf(x)+(x^n+1)g(x)=2^m$$

for some polynomials $f(x)$, $g(x)$ with integer coefficients, and hence

$$k_0=2^m.$$