How to prove that $x^{2n}+x^n+1$ has a factor $x^2+x+1$ if and only if $n \not\equiv 0 \bmod 3$？

Question

Well, I don't know whether it is exactly correct.I get this result when I was dealing with a simple problem "find out the factors of $x^{10}+x^5+1$". I put different $n$ into this polynomial and draw the roots in the complex plane by WolframAlpha: n=4,7,9

The distribution of these roots has certain rules: the red angle is half of the blue one, and one red angle comes after one blue angle and make up the whole circle in this way. By observing the pictures, we can easily get the result that is stated in the question.

The following question has been moved to another post:How to prove that $\sum_{i=0}^kx^{in}$ have a same factor $P(x)$ if and only if $n \not\equiv 0 \bmod (k+1)$？

[ Also, for $x^{3n}+x^{2n}+x^n+1$, I infer it has a factor $x^2+1$ if and only if $n\not \equiv 0\bmod 4$. Also see the pictures: n=2,3,4,5

My guess is: For polynomials $x^{kn}+x^{(k-1)n}+…+x^{2n}+x^n+1,k\geq2$, if $n\not \equiv 0\bmod (k+1)$, they all have a certain factor $P(x)$.

Is that true？How do I find the factor $P(x)$？How to prove？(I think the method of Cotes' Theorem may be used for it. See T. Needham, Visual Complex Analysis, pp 46-47) ]

Answer 1

Since $(x^2+x+1)(x-1)=x^3-1$ the roots of $(x^2+x+1)$ are $\{\zeta,\zeta^2\}$ where $\zeta$ is a primitive cubic root of $1$.

When $n\not\equiv 0\bmod 3$ there is an equality of sets $\{\zeta^n,\zeta^{2n}\}=\{\zeta,\zeta^2\}$ which shows that $\zeta$ and $\zeta^2$ are also roots of $x^{2n}+x^n+1$, thus the divisibility of polynomials.

On the other hand when $n\equiv0\bmod3$ we have $\zeta^n=\zeta^{2n}=1$ so $\{\zeta,\zeta^2\}$ are not roots of $x^{2n}+x^n+1$.

Answer 2

We can also see this in terms of the factorizations themselves. The "template" would be $ \ u^2 + u + 1 \ = \ \large{\frac{u^3 \ - \ 1}{u \ - \ 1}} \ \normalsize{, \ u \ \neq \ 1 \ \ .} \ $ As "base" examples, we have

$ \mathbf{n \ = \ 2 \ :} \quad x^4 \ + \ x^2 \ + \ 1 \ \ = \ \ \large{\frac{(x^2)^3 \ - \ 1}{x^2 \ - \ 1} \ \ = \ \ \frac{(x^3)^2 \ - \ 1}{x^2 \ - \ 1} \ \ = \ \ \frac{(x^3 \ - \ 1) \ · \ (x^3 \ + \ 1)}{(x \ - \ 1) \ · \ (x \ + \ 1)}} $

$ \quad \quad \quad \quad \quad = \ \ (x^2 \ + \ x \ + \ 1) \ · \ (x^2 \ - \ x \ + \ 1) \ \ , \ \ x^2 \ \neq \ 1 \ \ ; $

$ \mathbf{n \ = \ 4 \ :} \quad x^8 \ + \ x^4 \ + \ 1 \ \ = \ \ \large{\frac{(x^4)^3 \ - \ 1}{x^4 \ - \ 1} \ \ = \ \ \frac{(x^3)^4 \ - \ 1}{x^4 \ - \ 1} \ \ = \ \ \frac{( \ [x^3]^2 \ - \ 1 \ ) \ · \ ( \ [x^3]^2 \ + \ 1 \ )}{(x^2 \ - \ 1) \ · \ (x^2 \ + \ 1)}} $

$ \quad \quad \quad \quad \quad \large{= \ \ \frac{( \ [x^3]^2 \ - \ 1 \ ) \ · \ ( \ [x^2]^3 \ + \ 1 \ )}{(x \ - \ 1) \ · \ (x \ + \ 1) \ · \ (x^2 \ + \ 1)} \ \ = \ \ \frac{( \ x^3 \ - \ 1 \ ) \ · \ ( \ x^3 \ + \ 1 \ )\ · \ ( \ [x^2]^3 \ + \ 1 \ )}{(x \ - \ 1) \ · \ (x \ + \ 1) \ · \ (x^2 \ + \ 1)} } $

$ \quad \quad \quad \quad \quad = \ \ (x^2 \ + \ x \ + \ 1) \ · \ (x^2 \ - \ x \ + \ 1) \ · \ (x^4 \ - \ x^2 \ + \ 1) \ \ , \ \ x^4 \ \neq \ 1 \ \ ; $

for these polynomials, we are able to write the numerator in each quotient as a "difference of two squares", however,

$ \mathbf{n \ = \ 3 \ :} \quad x^6 \ + \ x^3 \ + \ 1 \ \ = \ \ \large{ \frac{(x^3)^3 \ - \ 1}{x^3 \ - \ 1} \ \ = \ \ \frac{( \ x^3 \ - \ 1 \ ) \ · \ ( \ x^6 \ + \ x^3 \ + \ 1 \ )}{(x^3 \ - \ 1) }} \ \ \normalsize{, \ \ x^3 \ \neq \ 1 \ \ ,} $

since we are unable to use a "difference of two squares"; it is easily checked that this polynomial is irreducible over $ \ \mathbb{R} \ \ . $

For the general cases, we actually need to consider the parity of $ \ n \ \ . $

$ \mathbf{n \ = \ 3m \pm 1 \ = \ 2p \ , \ 2p' \ :} \quad x^{4p} \ + \ x^{2p} \ + \ 1 \ \ = \ \ \large{\frac{(x^{2p})^3 \ - \ 1}{x^{2p} \ - \ 1} \ \ = \ \ \frac{(x^{3p})^2 \ - \ 1}{x^{2p} \ - \ 1} } $

$ \quad \quad \quad \quad \quad \large{= \ \ \frac{( \ x^{3p} \ - \ 1 \ ) \ · \ ( \ x^{3p} \ + \ 1 \ )}{(x^p \ - \ 1) \ · \ (x^p \ + \ 1)} \ \ = \ \ \frac{( \ (x^3)^p \ - \ 1 \ ) \ · \ ( \ x^{3p} \ + \ 1 \ )}{(x^p \ - \ 1) \ · \ (x^p \ + \ 1)} } $

$ \quad \quad \quad \quad \quad \large{ = \ \ \left( \frac{ x^3 \ - \ 1 }{x \ - \ 1} \right) \ · \ \frac{( \ [x^3]^{p - 1} \ + \ [x^3]^{p - 2} \ + \ \ldots \ + \ x^3 \ + \ 1 \ ) \ · \ ( \ x^{3p} \ + \ 1 \ )}{( \ x^{p - 1} \ + \ x^{p - 2} \ + \ \ldots \ + \ x \ + \ 1 \ ) \ · \ (x^p \ + \ 1)} } $

$ \quad \quad \quad \quad \quad = \ \ ( x^2 \ + \ x \ + \ 1 ) \ · \ \large{\frac{( \ [x^3]^{p - 1} \ + \ [x^3]^{p - 2} \ + \ \ldots \ + \ x^3 \ + \ 1 \ ) \ · \ ( \ x^{3p} \ + \ 1 \ )}{( \ x^{p - 1} \ + \ x^{p - 2} \ + \ \ldots \ + \ x \ + \ 1 \ ) \ · \ (x^p \ + \ 1)} } \ \ , \ \ \normalsize{x^{2p} \ \neq \ 1} \ \ , $

and similiarly for $ \ 2p' \ \ , $

$ \mathbf{n \ = \ 3m \ \ \text{[odd]} \ :} \quad x^{6m} \ + \ x^{3m} \ + \ 1 \ \ = \ \ \large{\frac{(x^{3m})^3 \ - \ 1}{x^{3m} \ - \ 1} \ \ = \ \ \frac{(x^{3m} \ - \ 1) \ · \ ( \ [x^{3m}]^2 \ + \ x^{3m} \ + \ + \ 1 \ ) }{x^{3m} \ - \ 1} } $

$ \quad \quad \quad \quad \quad = \ \ (x^{3m})^2 \ + \ x^{3m} \ + \ 1 \ \ = \ \ x^{6m} \ + \ x^{3m} \ + \ 1 \ \ , \ \ x^{3m} \ \neq \ 1 \ \ , $

which simply returns our polynomial, which is biquadratic in $ \ 3m \ $ and irreducible over $ \ \mathbb{R} \ \ ; $

$ \mathbf{n \ = \ 3m \pm 1 \ \ \text{[odd]} \ :} \quad x^{2n} \ + \ x^n \ + \ 1 \ \ = \ \ \large{\frac{x^{3n} \ - \ 1}{x^n \ - \ 1} \ \ = \ \ \frac{(x^3)^n \ - \ 1}{x^n \ - \ 1} } $

$ \quad \quad \quad \quad \quad \large{ = \ \ \left( \frac{ x^3 \ - \ 1 }{x \ - \ 1} \right) \ · \ \frac{ (x^3)^{n - 1} \ + \ (x^3)^{n - 2} \ + \ \ldots \ + \ x^3 \ + \ 1 }{x^{n - 1} \ + \ x^{n - 2} \ + \ \ldots \ + \ x \ + \ 1 } } $

$ \quad \quad \quad \quad \quad = \ \ ( x^2 \ + \ x \ + \ 1 ) \ · \ \large{\frac{ (x^3)^{n - 1} \ + \ (x^3)^{n - 2} \ + \ \ldots \ + \ x^3 \ + \ 1 }{x^{n - 1} \ + \ x^{n - 2} \ + \ \ldots \ + \ x \ + \ 1 } } \ \ , \ \ \normalsize{x^n \ \neq \ 1} \ \ , $

$ \mathbf{n \ = \ 3m \ = \ 6q \ :} \quad x^{12q} \ + \ x^{6q} \ + \ 1 \ \ = \ \ \large{\frac{(x^{6q})^3 \ - \ 1}{x^{6q} \ - \ 1} \ \ = \ \ \frac{(x^{6q} \ - \ 1) \ · \ ( \ [x^{6q}]^2 \ + \ x^{6q} \ + \ 1 \ ) }{x^{6q} \ - \ 1} } $

$ \quad \quad \quad \quad \quad = \ \ x^{12q} \ + \ x^{6q} \ + \ 1 \ \ = \ \ (x^{6q} \ + \ x^{3q} \ + \ 1) \ · \ (x^{6q} \ - \ x^{3q} \ + \ 1) \ \ , \ \ x^{6q} \ \neq \ 1 \ \ , $

which returns irreducible biquadratic factors, none of which are $ \ x^2 \ + \ x \ + \ 1 \ . \ $ A couple of examples of this latter case are

$ \mathbf{n \ = \ 5 \ :} \quad x^{10} \ + \ x^5 \ + \ 1 \ \ = \ \ \large{\frac{(x^5)^3 \ - \ 1}{x^5 \ - \ 1} \ \ = \ \ \left( \frac{ x^3 \ - \ 1 }{x \ - \ 1} \right) \ · \ \frac{ (x^3)^{5 - 1} \ + \ (x^3)^{5 - 2} \ + \ \ldots \ + \ x^3 \ + \ 1 }{x^{5 - 1} \ + \ x^{5 - 2} \ + \ \ldots \ + \ x \ + \ 1 } } $

$ \quad \quad \quad \quad \quad = \ \ ( x^2 \ + \ x \ + \ 1 ) \ · \ \large{\frac{ x^{12} \ + \ x^9 \ + \ x^6 \ + \ x^3 \ + \ 1 }{x^4 \ + \ x^3 \ + \ x^2 \ + \ x \ + \ 1 } } \ \ , \ \ \normalsize{x^5 \ \neq \ 1} \ \ , $

$ \mathbf{n \ = \ 6 \ :} \quad x^{12} \ + \ x^6 \ + \ 1 \ \ = \ \ (x^6 \ + \ x^3 \ + \ 1) \ · \ (x^6 \ - \ x^3 \ + \ 1) \ \ , \ \ x^6 \ \neq \ 1 \ \ . $

Viewed in this way, the zeroes of $ \ u^2 + u + 1 \ $ are the three unit-modulus zeroes of $ \ z^3 - 1 \ \ , \ \ z_k \ = \ e^{\ i·2k \pi/3} \ , $ $ k \ = \ 0 \ , \ 1 \ , \ 2 \ \ , $ with $ \ z_0 \ = \ 1 \ $ "removed". Finding the zeroes of $ \ w^{2n} + w^n + 1 \ $ substitutes $ \ u \ = \ w^n \ \ , \ \ $ generating three "families" of $ n-$th-roots,

• $ \quad w^n \ = \ z_0 \ \Rightarrow \ \large{w_{0 \ , \ j} \ = \ e^{\ i·[0 \ + \ 2j\pi]/n} \ = \ e^{\ i·6j\pi/(3n)} } \ \ , \ \ \normalsize{0 \ \le \ j \ \le \ n - 1 \ \ ,} \ $ which are excluded by the condition $ \ z^n \ \neq \ 1 \ \ ; $

• $ \quad w^n \ = \ z_1 \ \Rightarrow \ \large{w_{1 \ , \ j} \ = \ e^{\ i·[(2\pi / 3) \ + \ 2j)\pi]/n} } \ = \ e^{\ i·(2 + 6j)\pi/(3n)} \ \ , \ \ \normalsize{0 \ \le \ j \ \le \ n - 1 \ \ ;} $

• $ \quad w^n \ = \ z_2 \ \Rightarrow \ \large{w_{2 \ , \ j} \ = \ e^{\ i·[(4\pi / 3) \ + \ 2j)\pi]/n} } \ = \ e^{\ i·(4 + 6j)\pi/(3n)} \ \ , \ \ \normalsize{0 \ \le \ j \ \le \ n - 1 \ \ .} $

This produces the $ \ 2n \ $ complex zeroes expected for the polynomial.

For $ \ n \ = \ 3m \pm 1 \ \ , \ $ it is possible to find integer solutions for $ \ j \ $ in either $ \ \large{\frac{(2 \ + \ 6 j)· \pi}{3n} \ = \ \frac{2 \pi}{3} \ , \ \frac{4 \pi}{3} \ \Rightarrow \ j \ = \ \frac{n - 1}{3} \ , \ \frac{2n - 1}{3} } \ $ or $ \ \large{\frac{(4 \ + \ 6 \pi)· j}{3n} \ = \ \frac{2 \pi}{3} \ , \ \frac{4 \pi}{3} \ \Rightarrow \ j \ = \ \frac{n - 2}{3} \ , \ \frac{2n - 2}{3} } \ \ , \ \normalsize{0 \ \le \ j \ \le \ n - 1 \ \ .} $ So the zeroes of $ \ z^2 + z + 1 \ $ are found among those of $ \ w^{2n} + w^n + 1 \ \ . $ But for $ \ n \ = \ 3m \ \ , \ $ the zeroes become $ \ \large{e^{\ i·(2 + 6j)\pi/(9m)} \ \ , \ \ e^{\ i·(4 + 6j)\pi/(9m)} } \ \ $ and $ \ \large{j \ = \ \frac{18m - 2}{6} \ , \ \frac{36m - 2}{6} \ , \ \frac{18m - 4}{6} \ , \ \frac{36m - 4}{6} } \ $ are no longer integers. Hence, the zeroes of $ \ z^2 + z + 1 \ $ are not zeroes of $ \ w^{6m} + w^{3m} + 1 \ \ . $