Let $ n$ be an even positive integer. Prove that there exists a positive inter $ k$ such that \[ k = f(x) \cdot (x+1)^n + g(x) \cdot (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,$ i.e. show that $ k_0 = 2^q$ where $ q$ is the odd integer determined by $ n = q \cdot 2^r, r \in \mathbb{N}.$ Note: This is variant A6' of the three variants given for this problem.
Problem
Source: IMO Shortlist 1996, A6
Tags: algebra, polynomial, function, IMO Shortlist
BaBaK Ghalebi
11.09.2008 23:15
" wrote: note that $ n$ is an even number so $ (x + 1)$ divides $ 1 - x^n$,so there exists a polynomial $ a(x)$ with integer coefficients such that: $ (1 + x)\cdot a(x) = 1 - x^n = 2 - (1 + x^n)$ $ \Rightarrow 2 = (1 + x)\cdot a(x) + (1 + x^n)$ $ \Rightarrow 2^n = (1 + x)^n\cdot\left(a(x)\right)^n + (1 + x^n)\cdot b(x)$ where $ b(x)$ is a polynomial with integer coefficients,as wanted. now let $ f(x),g(x)$ be two polynomials with integer coefficients such that: $ k_0 = f(x)\cdot (x + 1)^n + g(x)\cdot(x^n + 1)\textrm{ (1)}$ now let $ n = q2^r$ where $ q$ is an odd integer,we'll show that $ k_0 = 2^q$.put $ t = 2^r$ and note that $ x^n + 1 = (x^t + 1)\cdot Q(x)$ in which: $ Q(x) = x^{t(q - 1)} - x^{t(q - 2)} + \ldots - x^t + 1$ so $ Q( - 1) = 1$,now the roots of the equation $ x^t + 1 = 0$ are: $ w_m = \cos\left(\frac {(2m - 1)\pi}{t}\right) + \sin\left(\frac {(2m - 1)\pi}{t}\right)\textrm{ , } m = 1,2,\ldots ,t$ now according to $ (1)$ we get that: $ f(w_m)\cdot (w_m + 1)^n = k_0\textrm{ }1\leq m\leq t\textrm{ (2)}$ now note that $ (w_1 + 1)(w_2 + 1)\cdots (w_t + 1) = 2$,now we can see that: $ f(w_1)\cdots f(w_m) = F$ where $ F$ is an integer,now according to $ (2)$ we get that: $ 2^nF = k_0^t$,so $ k_0$ is divisible by $ 2^q$,now from the fact that $ Q( - 1) = 1$ we get that: $ Q(x) = (x + 1)\cdot c(x) + 1$ where $ c(x)$ has integer coefficients,thus: $ (x + 1)^n\cdot\left(c(x)\right)^n = \left( - 1 + Q(x)\right)^n = 1 + Q(x)\cdot d(x)\textrm{ (3)}$ in which $ d(x)$ is a polynomial with integer coefficients,now note that for a fixed number $ m$,the powers $ w_m^{2j - 1}$ for $ 1\leq j\leq t$ are different and also form all the roots of $ x^t + 1 = 0$,so: $ (1 + w_m)(1 + w_m^3)\cdots (1 + w_m^{2t - 1}) = 2$ and $ (1 + w_m^{2j - 1}) = (1 + w_m)\left(1 - w_m + w_m^2 - \ldots + w_m^{2j - 2}\right)$ so there exists a polynomial $ h(x)$ with integer coefficients,independent from $ m$,such that: $ (1 + w_m)^t\cdot h(w_m) = 2$ so $ (x + 1)^t\cdot h(x) - 2$ is divisible by $ x^t + 1$ and we can write: $ (x + 1)^t\cdot h(x) = 2 + (x^t + 1)\cdot g(x)$ in which $ g(x)$ is a polynomial with integer coefficients,so: $ (x + 1)^n\cdot\left(h(x)\right)^q = 2^q + (x^t + 1)\cdot w(x)\textrm{ (4)}$ in which $ w(x)$ is a polynomial with integer coefficients,now using $ (3),(4)$ together,we obtain that: \begin{eqnarray*}(x + 1)^n\cdot\left(c(x)\right)^n\cdot (x^t + 1)\cdot w(x) & = & (x^t + 1)\cdot w(x) + (x^t + 1)\cdot w(x)\cdot Q(x)\cdot d(x) \\ & = & (x + 1)^n\cdot\left(h(x)\right)^q - 2^q + (x^n + 1)\cdot w(x)\cdot d(x) \\ & \Rightarrow & 2^q = p(x)\cdot (x + 1)^n + q(x)\cdot (x^n + 1)\end{eqnarray*} in which $ p(x),q(x)$ have integer coefficients,so $ k_0\leq 2^q$ but we had $ 2^q\mid k_0$,hence $ k_0 = 2^q$. QED
trigg
20.06.2009 10:57
I like this problem it is really nice solution is good I like it
Thinkertoys
30.04.2011 01:02
I understood the whole solution, except one small step: why is $ f(w_{1})\cdots f(w_{m}) = F $ an integer? Can someone explain me this step with more detail? Thanks in advance Thinkertoys
Zhero
15.12.2011 01:34
$f(w_1) f(w_2) \cdots f(w_n)$ is an integer by the fundamental theorem of symmetric polynomials. We can express $f(w_1) f(w_2) \cdots f(w_n)$ as a symmetric polynomial with integer coefficients evaluated at the symmetric sums of $w_1, w_2, \ldots, w_n$, which, by Vieta's formulas, are themselves integers. Anyway, here is another way to show that a minimum of $2^q$ can be attained.
First, we show that the minimum, $k$, is a power of 2. Because $x+1$ divides $x^n - 1$, we have $x^n - 1 = a(x) (x+1)$, or $2 = (x^n+1) - a(x)(x+1)$. Raising both sides to the $n$th power, we have
\[ 2^n = a(x)^n (x+1)^n + b(x)(x^n + 1). \, \, \,\, \, \,\, \, \, (1)\]
for some polynomial $b(x)$ (which we obtain from binomially expanding the sum and factoring out $x^n+1$ from all but the $a(x)^n (x+1)^n$ term.) It follows that some minimal $k$ with
\[ k = f(x) (x+1)^n + g(x)(x^n + 1) \, \, \,\, \, \,\, \, \, (2) \]
exists. Now, if we subtract (2) $\lfloor 2^n/k \rfloor$ times from (1), the left-hand side must be 0 (or else the minimality of $k$ is contradicted), so $k$ must divide $2^n$, i.e,. $k$ must be a power of 2.
We now show that when $q=1$, we must have $k=2$. First, by substituting $x=1$, it is easy to see that $k$ must be even. Now suppose for the sake of contradiction that $k=2^c$ for some $c \geq 2$. Let $h(x) = -g(x)$. Our new equation is
\[ 2^c = f(x) (x+1)^{2^r} - h(x) (x^{2^r}+1). \, \, \,\, \, \,\, \, \, (3) \]
It is clear that $\deg f = \deg h$. Let $f(x) = (x^{2^r} + 1)u(x) + v(x)$, with $\deg r(x) < 2^r$. Because we can replace $f(x)$ and $h(x)$ with $f(x)-u(x)(x^{2^r}+1) = v(x)$ and $h(x) + u(x)(x+1)^{2^r}$, respectively, we can suppose without loss of generality that $\deg f = \deg h < 2^r$.
Consider this equation in the finite field $F_2$, i.e., the finite field of order 2. $f$ and $h$ cannot be the zero polynomial in $F_2$, or else we can divide (3) by 2 to obtain a smaller $k$. Equation (3) taken in $F_2$ yields
\[ f(x)(x+1)^{2^r} = h(x)(x^{2^r}+1). \, \, \,\, \, \,\, \, \, (4) \]
Since $(x+1)^{2^r} = x^{2^r} + 1$ in $F_2$, we have
\[ (x^{2^r} + 1)(f(x) - h(x)) = 0 \]
in $F_2$. Since $x^{2^r} + 1$ is nonzero in $F_2$, we must have $f(x)-h(x) = 0$ in $F_2$, i.e., we must have $f(x) = h(x) + 2p(x)$ for some integer polynomial $p$. Substituting this into (3), we have
\[ 2^c = h(x)((x+1)^{2^r} - (x^{2^r} + 1)) + 2p(x)(x+1)^{2^r}. \, \, \,\, \, \,\, \, \, (5) \]
Let $e(x) =((x+1)^{2^r} - (x^{2^r} + 1))/2$. Note that $e$ is an integer polynomial, and that $e(1) = 2^{2^r - 1} - 1$ is odd. Dividing (5) by 2 gives
\[ 2^{c-1} = h(x)e(x) + p(x)(x+1)^{2^r}. \, \, \,\, \, \,\, \, \, (6) \]
Because $c \geq 2$, $2^{c-1}$ is even. Thus, if we consider (6) in $F_2$, we get
\[ p(x)(x+1)^{2^r} = (-h(x))(e(x)). \]
Since $e(1)$ is odd, the polynomials $(x+1)^{2^r}$ and $e(x)$ are coprime in $F_2$. Thus, $(x+1)^{2^r}$ divides $-h(x)$ in $F_2$, so there exist polynomials $c(x)$ and $d(x)$ such that $h(x) = c(x)(x+1)^{2^r} + 2d(x)$. But this implies that either $\deg h \geq 2^r$ or $h$ is the zero polynomial in $F_2$, both of which are contradictions. Thus, our assumption that $c \geq 2$ is false, so we must have $k=2$.
We now prove the result for all $q$. Suppose we have polynomials $f(x)$ and $g(x)$ such that
\[ 2 = f(x) (x+1)^{2^r} + g(x)(x^{2^r} + 1). \]
Raise both sides to the $q$th power to get
\[ 2^q = f_0(x)(x+1)^{q 2^r} + g_0(x)(x^{2^r}+1), \]
where $f_0(x) = f(x)^q$ and $g_0(x)$ is obtained from binomially expanding and factoring $x^{2^r} + 1$ out of all the terms but $f_0(x) (x+1)^{q 2^r}.$ Now replace $x$ with $x^q$ to get
\[ 2^q = f_0(x^q) (x^q + 1)^{q 2^r} + g_0(x^q) (x^{q 2^r} + 1) = \left( f_0(x^q) \frac{x^q+1}{x+1}\right)^{q 2^r} (x+1)^{q 2^r} + g_0(x^q) (x^{q 2^r} + 1), \]
so our construction is complete.
mathocean97
17.06.2015 18:00
As above, I'll prove that $k = 2^q$, where $n = q \cdot 2^r$, and $q$ is odd, and $r$ is an integer greater than or equal to 0. There are many examples of the construction for $k = 2^q$ above, so I'll just give my solution for proving the lower bound: $k \ge 2^q$ Obviously, we want that for any integer $x$, $\gcd((x+1)^n, x^n+1) \ge k$. This looks bad initially, because for any integers $x$, $\gcd((x+1)^n, x^n+1) \le 2$. So instead of using only integers for $x$, why not use algebraic integers? Remember that the algebraic integers forma ring, i.e. the sum or product of any two algebraic integers is an algebraic integer. Our algebraic integers here will just use roots of unity. Let $\omega = e^{\frac{\pi i}{2^r}}$. Note that $\omega^n + 1 = 0$. Let's turn to evaluating $(\omega + 1)^n$. $\omega + 1 = (\cos \left( \frac{\pi }{2^r} \right) + 1) + i \sin \left( \frac{\pi }{2^r} \right) = 2 \cos \left( \frac{\pi }{2^{r+1}} \right) e^{\frac{\pi i}{2^{r+1}} }.$ Therefore, $(\omega+1)^n = 2^n \cos ^n \left( \frac{\pi }{2^{r+1}} \right) i^q$, by simple computations. Let's ignore the $i^q$ at the end, and just focus on $2^n \cos ^n \left( \frac{\pi }{2^{r+1}} \right)$. The previous expression equals $\left( 2^{2^r} \cos ^{2^r} \left( \frac{\pi }{2^{r+1}} \right) \right)^q$. Let $\alpha = \frac{1}{2} \left( 2^{2^r} \cos ^{2^r} \left( \frac{\pi }{2^{r+1}} \right) \right) = 2^{2^r-1} \cos ^{2^r} \left( \frac{\pi }{2^{r+1}} \right)$. I claim that $\alpha$ is an algebraic integer. We prove this by induction on $r$. The base case $r = 0$ is obviously true. Note that \[2^{2^r-1} \cos ^{2^r} \left( \frac{\pi }{2^{r+1}} \right) = 2^{2^r-1} \left(\frac{1+\cos \left(\frac{\pi}{2^r} \right)}{2} \right)^{2^{r-1}} = 2^{2^{r-1}-1} ( 1+\cos \left(\frac{\pi}{2^r} \right) )^{2^{r-1}}, \] using the cosine double angle identity. The fact that the previous expression is an algebraic integer then comes from implicitly expanding the binomial theorem and using the inductive hypothesis. Therefore, $\left( 2^{2^r} \cos ^{2^r} \left( \frac{\pi }{2^{r+1}} \right) \right)^q = (2 \alpha)^q = 2^q \alpha^q.$ Therefore, $(\omega+1)^n = 2^q \cdot \alpha^q \cdot i^q$. Since $f(\omega) (\omega+1)^n + g(\omega) (\omega^n+1) = f(\omega)(\omega+1)^n = k$, and $f(\omega)$ is an algebraic integer, and $(\omega+1)^n = 2^q \cdot \alpha^q \cdot i^q$, $k$ must be a multiple of $2^q$. I'll leave the construction to the other posts. Mine was the same.
pi37
23.03.2016 16:09
First, we prove that if the expression is an integer, it's divisible by $2^q$. Let $\omega=e^{\pi i / n}$, so the roots of $x^n+1$ are $\omega,\omega^3,\cdots \omega^{2n-1}$. Now if $k=f(\omega)(\omega+1)^n$, then for any conjugate $\omega'=\omega^{2j-1}$ of $\omega$, $k=f(\omega')(\omega'+1)^n$ as well. So \begin{align*} k^{2^r}&=f(\omega^{q})(\omega^{q}+1)^n f(\omega^{3q})(\omega^{3q}+1)^n \cdots f(\omega^{(2^{r+1}-1)q})(\omega^{(2^{r+1}-1)q}+1)^n\\ &=h(-1)^n f(\omega^q)f(\omega^{3q})\cdots f(\omega^{(2^{r+1}-1)q})\\ &=2^n f(\omega^q)f(\omega^{3q})\cdots f(\omega^{(2^{r+1}-1)q}) \end{align*}where $h(x)=x^{2^r}+1$. Now $ f(\omega^q)f(\omega^{3q})\cdots f(\omega^{(2^{r+1}-1)q})$ is both an algebraic integer and rational, so it is an integer. Thus $2^{2^r q}=2^n\mid k^{2^r}$, implying $2^q\mid k$. Now we show that $k=2^q$ can be constructed in the given form. It suffices to find $f\in \mathbb{Z}[x]$ such that $2^q=f(\omega) (\omega+1)^n$. Take $f$ such that \[ f(x)\cdot (x+1)^n=\left((x^q+1)(x^{3q}+1)\cdots (x^{(2^{r+1}-1)q}+1)\right)^{q} \](Observe that the right hand side has $2^r\cdot q = n$ factors of $(x+1)$.) As before, then, \[ f(\omega)\cdot (\omega+1)^n = h(-1)^q=2^q \]