I Lemma regarding polynomials with one for all coefficients

[jack476]

I managed to get through all of the problems in chapter three of Problem Solving through Problems, and I am now on to chapter 4 in the section on polynomials. A few problems I have encountered so far involve polynomials of the form:

P(x) = 1 + x + x² + x³ +...+xⁿ

I noticed that when n, the degree of the polynomial, is a sum of the first k powers of two (starting from 0), then P(x) can be factored as such:

P(x) = (x+1)(x²+1)(x⁴ + 1)...(x^2k + 1)

For example, 7 = 2⁰ + 2¹ + 2² so:

1 + x² + x³ + ... + x⁷ = (x + 1)(x²+1)(x⁴ + 1)

Furthermore, if the powers in the polynomial are successive multiples of m (starting from 0) then the powers in the factorization are the first k powers of two times m, for example:

1 + x⁴ + x⁸ + x¹² = (x⁴+1)(x⁸+1)

Lastly, the same is true for an arithmetic progression of powers if the lowest power can be factored out to leave the appropriate form, for example:

x² + x³ + x⁴ + x⁵ = x²(1 + x + x² + x³) = x²(x + 1)(x²+1)

A proof of this lemma would be immensely useful, because if it is true then it provides extremely clean solutions to a number of the problems in the chapter, but I'm at a loss as to how to prove it.

 

[fresh_42]

Have you divided $\sum_{i=0}^{n} x^{ip}$ by $x^n + 1$? Did you mean this?

 

[jack476]

That gave me an idea for an induction proof, I'll give it a try when I get back from work. Thanks :)

 

[Svein]

Try multiplying P(x) with (x - 1)...

 

[jack476]

Sorry that it took me a long time to get back to this, but I was able to find a more general proof. If P(x) is an all-one polynomial whose powers form a complete arithmetic progression, or are successive multiples, then if the number of terms in P(x) is not prime, it can be factored with no remainder into a product of other all-one polynomials whose numbers of terms are equal to the prime factors of the total number of terms. I'll attach my attempt at a proof.