factoring all-one polynomials using the grouping method

The method of grouping terms can be used to factor all-one polynomials, i.e. polynomials of the form

$$\sum _{m=0}^{n-1}{x}^m$$

when $n$ is composite. (When $n$ is prime, these polynomials are irreducible, so there is nothing to do in that case.)

Let us consider a few examples:

$n=4$:

$1+x+x^2+x^3=$

$(1+x)+(x^2+x^3)=$

$(1+x)+x^2(1+x)=$

$(1+x)(1+x^2)$

$n=6$:

$1+x+x^2+x^3+x^4+x^5=$

$(1+x+x^2)+(x^3+x^4+x^5)=$

$(1+x+x^2)+x^3(1+x+x^2)=$

$(1+x^3)(1+x+x^2)$

$n=8$:

$1+x+x^2+x^3+x^4+x^5+x^6+x^7=$

$(1+x+x^2+x^3)+(x^4+(x^5+x^6+x^7)=$

$(1+x+x^2+x^3)+x^4(1+x+x^2+x^3)=$

$(1+x^4)(1+x+x^2+x^3)$

Combining this result with the factorization we have for the case $n=4$, we obtain the following:

$1+x+x^2+x^3+x^4+x^5+x^6+x^7=$

$(1+x)(1+x^2)(1+x^4)$

$n=9$:

$1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8=$

$(1+x+x^2)+(x^3+x^4+x^5)+(x^6+x^7+x^8)=$

$(1+x+x^2)+x^3(1+x+x^2)+x^6(1+x+x^2)=$

$(1+x+x^2)(1+x^3+x^6)$

$n=12$:

$1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}=$

$(1+x+x^2)+(x^3+x^4+x^5)+(x^6+x^7+x^8)+(x^9+x^{10}+x^{11})=$

$(1+x+x^2)+x^3(1+x+x^2)+x^6(1+x+x^2)+x^9(1+x+x^2)=$

$(1+x+x^2)(1+x^3+x^6+x^9)=$

$(1+x+x^2)((1+x^3)+(x^6+x^9))=$

$(1+x+x^2)((1+x^3)+x^6(1+x^3))=$

$(1+x+x^2)(1+x^3)(1+x^6)$

It might be worth pointing out that the polynomials produced by this factorization are not all irreducible. For instance,

$$1+x^3=(1+x)(1-x+x^2).$$

However, to obtain this factorization, one needs to use some techique other than the grouping method. Likewise. the polynomial $1+x^6$ is also reducible.

Title	factoring all-one polynomials using the grouping method
Canonical name	FactoringAllonePolynomialsUsingTheGroupingMethod
Date of creation	2013-03-22 15:06:52
Last modified on	2013-03-22 15:06:52
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	13
Author	rspuzio (6075)
Entry type	Example
Classification	msc 13P05
Related topic	AllOnePolynomial
Related topic	CyclotomicPolynomial