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 + x2 + x3 +....+xn

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)(x2+1)(x4 + 1)....(x2k + 1)

For example, 7 = 20 + 21 + 22 so:

1 + x2 + x3 + .... + x7 = (x + 1)(x2+1)(x4 + 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 + x4 + x8 + x12 = (x4+1)(x8+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:

x2 + x3 + x4 + x5 = x2(1 + x + x2 + x3) = x2(x + 1)(x2+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

Mentor
2018 Award
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 and mfb

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.

Attachments

• 51 KB Views: 66
• Math_QED

"Lemma regarding polynomials with one for all coefficients"

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving