Let \[f = X^{n}+a_{n-1}X^{n-1}+\ldots+a_{1}X+a_{0}\] be an integer polynomial of degree $n \geq 3$ such that $a_{k}+a_{n-k}$ is even for all $k \in \overline{1,n-1}$ and $a_{0}$ is even. Suppose that $f = gh$, where $g,h$ are integer polynomials and $\deg g \leq \deg h$ and all the coefficients of $h$ are odd. Prove that $f$ has an integer root.
Problem
Source: Romanian TST 2 2007, Problem 1
Tags: algebra, polynomial, algebra proposed
15.04.2007 21:43
You can prove g is linear by considering it in $\mathbb{Z}_{2}[x]$. The trick is that if h(x) divides f(x), then h(x) also divides $x^{n}f \left( \frac{1}{x}\right)$ (in $\mathbb{Z}_{2}[x]$). Edit, ok... as perfect_radio requested, I will provide further details. For this solution we'll be working only in $\mathbb{Z}_{2}[x]$. We have $f(x) \equiv g(x)h(x)$ and since $h(x) \equiv h(1/x) \cdot x^{\deg h}$, we also have $h(x)g(1/x)x^{\deg g}\equiv f(1/x)x^{n}$. Notice that since $a_{k}+a_{n-k}\equiv 0$, we have $f(1/x)x^{n}+f(x) \equiv x^{n}+1$. Now let $\deg h = d$, and we know $d \ge \frac{n}{2}$. By solving for the coefficients of g, we find that the first few are $g(x) = 1+x+x^{d+1}+x^{d+2}+\ldots$. However, if $\deg g \ge d+1$, then $\deg g+\deg h = 2d+1 > n$, so we must have $g(x) = 1+x$. So that pretty much shows that g is linear in $\mathbb{Z}[x]$, although we should probably also note that the leading coefficient on g must be odd (so that it doesn't vanish when reducing to $\mathbb{Z}_{2}[x]$).
31.12.2007 07:55
probability1.01 wrote: so we must have $ g(x) = 1 + x$. So that pretty much shows that g is linear in $ \mathbb{Z}[x]$, although we should probably also note that the leading coefficient on g must be odd (so that it doesn't vanish when reducing to $ \mathbb{Z}_{2}[x]$). Since we're working in $ \mathbb{Z}_{2}[x]$, don't you just know the coefficients are congruent to $ 1 + x (\mod 2)$?
15.01.2008 13:08
Can anybody explain, or I'm misunderstanding something?
28.01.2008 09:04
Well, I don't get it either.
07.08.2008 12:21
I think that's clear as the leading coefficient of g must be odd and divides 1 so it must no other way be 1. However,solving the coefficients is really boring to me!!Could anyone kindly and have enough time to clarify it! It remind me of failing to finish Problem 5 at the VMO 06!I wasnt able to end it!
09.08.2008 15:17
The cruelest solution is this: In $ \mathbb Z \slash 2 \mathbb Z$ we have $ f = gh = \left( b_0 + b_1 x + \ldots + b_j x^j \right) \left( 1 + x + \ldots + x^k \right)$, where $ j \leq k$. The coefficient of $ x^{j - 1}$ is $ a_{j - 1} = b_0 + \ldots + b_{j - 1}$ and the coefficient of $ x^{k + 1}$ is $ a_{k + 1} = b_1 + \ldots + b_j$. If $ j - 1 \geq 1$, then $ a_{j - 1} \equiv a_{k + 1} \left( \bmod \, 2 \right)$, so $ b_0 \equiv b_j \equiv 1 \left( \bmod \, 2 \right)$, contradiction with $ g(0) = 0$. Thus, $ j = 1$ and that's it.