Lemma regarding polynomials with one for all coefficients

  • I
  • Thread starter jack476
  • Start date
  • #1
314
122

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.
 

Answers and Replies

  • #2
12,890
9,533
Have you divided ##\sum_{i=0}^{n} x^{ip}## by ##x^n + 1##? Did you mean this?
 
  • #3
314
122
That gave me an idea for an induction proof, I'll give it a try when I get back from work. Thanks :)
 
  • #4
Svein
Science Advisor
Insights Author
2,068
662
Try multiplying P(x) with (x - 1)...
 
  • Like
Likes jack476 and mfb
  • #5
314
122
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

  • Like
Likes Math_QED

Related Threads on Lemma regarding polynomials with one for all coefficients

Replies
1
Views
405
Replies
8
Views
887
  • Last Post
Replies
6
Views
5K
Replies
5
Views
3K
Replies
1
Views
2K
Replies
12
Views
2K
  • Last Post
Replies
1
Views
1K
Replies
2
Views
601
Replies
2
Views
3K
Top