# Lemma regarding polynomials with one for all coefficients

• I

## Main Question or Discussion Point

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
Have you divided ##\sum_{i=0}^{n} x^{ip}## by ##x^n + 1##? Did you mean this?

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
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: 77
• Math_QED