Let $P(x)$ be a polynomial with real coefficients. Show that there exists a nonzero polynomial $Q(x)$ with real coefficients such that $P(x)Q(x)$ has terms that are all of a degree divisible by $10^9$.

2. Originally Posted by usagi_killer
Let $P(x)$ be a polynomial with real coefficients. Show that there exists a nonzero polynomial $Q(x)$ with real coefficients such that $P(x)Q(x)$ has terms that are all of a degree divisible by $10^9$.
Here's one way to approach this problem. To get an idea of what is involved, start with a simpler problem.

Let $\color{blue}P(x)$ be a polynomial with real coefficients. Show that there exists a nonzero polynomial $\color{blue}Q(x)$ with real coefficients such that $\color{blue}P(x)Q(x)$ has terms that are all of a degree divisible by 2.

A bit of thought shows that this is not too hard. Split P(x) into terms of even degree and terms of odd degree. Then we can write $P(x) = A(x) + xB(x)$, where both A(x) and B(x) have all terms of even degree. If $Q(x) = A(x)- xB(x)$ then $P(x)Q(x) = (A(x) + xB(x))(A(x) - xB(x)) = (A(x))^2 - x^2(B(x))^2$, which has all terms of even degree, as required. For convenience later on, define $P_2(P(x)) = P(x)Q(x)$.

Now try something a bit harder.

Let $\color{blue}P(x)$ be a polynomial with real coefficients. Show that there exists a nonzero polynomial $\color{blue}Q(x)$ with real coefficients such that $\color{blue}P(x)Q(x)$ has terms that are all of a degree divisible by 3.

Let $\omega = e^{2\pi i/3}$, a complex cube root of unity. Check that if $a+bx+cx^2$ is a real quadratic polynomial then $(a+bx+cx^2)(a+\omega bx+\omega^2 cx^2)(a+\omega^2 bx+\omega cx^2)$ has terms that are all of a degree divisible by 3. Also, the second and third of those three factors are complex conjugates of each other, so their product is a real polynomial.

For a general polynomial P(x), we can write $P(x) = A(x) + xB(x) + x^2C(x)$, where each of A(x), B(x) and C(x) has terms that are all of a degree divisible by 3. Let $Q(x) = (A(x)+\omega xB(x)+\omega^2 x^2C(x))(A(x)+\omega^2 xB(x)+\omega x^2C(x))$. Then $P_3(P(x)) = P(x)Q(x)$ is a multiple of P(x) whose terms are all of a degree divisible by 3.

The next part of the project is to do the same thing with 3 replaced by 5. You obviously have to start with a fifth complex root of unity, $\omega=e^{2\pi i/5}$, and the argument gets a bit tedious, so I'll skip it. The end result is a real polynomial Q(x) (a product of four complex factors) such that $P_5(P(x)) = P(x)Q(x)$ is a multiple of P(x) whose terms are all of a degree divisible by 5.

Now you can start to stitch things together. Notice that $P_{10}(x) = P_5(P_2(P(x)))$ is a multiple of P(x) whose terms are all of a degree divisible by 10. Then inductively define $P_{10^{k+1}}(P(x)) = P_{10}(P_{10^k}(P(x)))$. So finally, $P_{10^9}(P(x))$ is a multiple of P(x) whose terms are all of a degree divisible by $10^9$.

3. Wow! Amazing, A pertect application of the unit roots!
How can you image this stuff?