# 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$:

 $\displaystyle 1+x+x^{2}+x^{3}=$ $\displaystyle(1+x)+(x^{2}+x^{3})=$ $\displaystyle(1+x)+x^{2}(1+x)=$ $\displaystyle(1+x)(1+x^{2})$

$n=6$:

 $\displaystyle 1+x+x^{2}+x^{3}+x^{4}+x^{5}=$ $\displaystyle(1+x+x^{2})+(x^{3}+x^{4}+x^{5})=$ $\displaystyle(1+x+x^{2})+x^{3}(1+x+x^{2})=$ $\displaystyle(1+x^{3})(1+x+x^{2})$

$n=8$:

 $\displaystyle 1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+x^{7}=$ $\displaystyle(1+x+x^{2}+x^{3})+(x^{4}+(x^{5}+x^{6}+x^{7})=$ $\displaystyle(1+x+x^{2}+x^{3})+x^{4}(1+x+x^{2}+x^{3})=$ $\displaystyle(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:

 $\displaystyle 1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+x^{7}=$ $\displaystyle(1+x)(1+x^{2})(1+x^{4})$

$n=9$:

 $\displaystyle 1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+x^{7}+x^{8}=$ $\displaystyle(1+x+x^{2})+(x^{3}+x^{4}+x^{5})+(x^{6}+x^{7}+x^{8})=$ $\displaystyle(1+x+x^{2})+x^{3}(1+x+x^{2})+x^{6}(1+x+x^{2})=$ $\displaystyle(1+x+x^{2})(1+x^{3}+x^{6})$

$n=12$:

 $\displaystyle 1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+x^{7}+x^{8}+x^{9}+x^{10}+x^{11}=$ $\displaystyle(1+x+x^{2})+(x^{3}+x^{4}+x^{5})+(x^{6}+x^{7}+x^{8})+(x^{9}+x^{10}% +x^{11})=$ $\displaystyle(1+x+x^{2})+x^{3}(1+x+x^{2})+x^{6}(1+x+x^{2})+x^{9}(1+x+x^{2})=$ $\displaystyle(1+x+x^{2})(1+x^{3}+x^{6}+x^{9})=$ $\displaystyle(1+x+x^{2})((1+x^{3})+(x^{6}+x^{9}))=$ $\displaystyle(1+x+x^{2})((1+x^{3})+x^{6}(1+x^{3}))=$ $\displaystyle(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 FactoringAllonePolynomialsUsingTheGroupingMethod 2013-03-22 15:06:52 2013-03-22 15:06:52 rspuzio (6075) rspuzio (6075) 13 rspuzio (6075) Example msc 13P05 AllOnePolynomial CyclotomicPolynomial