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]$).

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)$?

Can anybody explain, or I'm misunderstanding something?

Well, I don't get it either.

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!

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.