Spotting that $\,x^8 + x^7 + 1\,$ is reducible.

Question

I saw a puzzle recently that came down to spotting that $\,x^8 + x^7 + 1\,$ is reducible — namely, we have

$$x^8 + x^7 + 1 = \left(1 + x + x^2\right)\left(1-x+x^3-x^4+x^6\right)$$

After playing around a bit, I noticed that this is a special case of the fact that

$$\left.\Phi_m\left(x\right) \quad \big| \quad x^{mk} \big[\Phi_m\left(x\right) - 1\big] + 1\right.$$

for each $k$, which holds since

$$x^{mk} \big[\Phi_m\left(x\right) - 1\big] + 1 = x^{m k} \Phi_m\left(x\right) + \left(1 - x^{m k}\right)$$

and of course both terms on the RHS are divisible by $\,\Phi_m\left(x\right)$. In the cases $\,m = 1, 2, 3\,$ this recovers the statements:

• $x-1\;$ divides $\;x^{k+1} - 1$
• $x+1\;$ divides $\;x^{2k+1} + 1$
• $x^2 + x + 1\;$ divides $\;x^{3k+2} + x^{3k+1} + 1$

Of course the first two are very well-known. Is it simply the case that many people also know the third statement off the tops of their heads? Or is there some other way of spotting that $x^8 + x^7 + 1$ is reducible?

Answer 1

The trick is that $8 \equiv 2 \pmod 3$ and $7 \equiv 1 \pmod 3.$ That means that, if we take a cube root of unity, say $$ \omega = \frac{-1 + i \sqrt 3}{2}, $$ we get $$ \omega^8 + \omega^7 + 1 = \omega^2 + \omega + 1 = 0. $$ The same holds for $$ \bar{\omega } = \omega^2. $$ That means that $$ (x - \omega)(x - \bar{\omega}) = x^2 + x + 1 $$ divides the original polynomial, as the quadratic is the minimal polynomial for $\omega.$

As you noticed, the same thing can be done with other roots of unity. If we had $$ x^{1347} + x^{949} + x^{216} + x^{98} + 1, $$ the exponents are $2,4,1,3 \pmod 5,$ and the displayed polynomial is divisible by $$ x^4 + x^3 + x^2 + x + 1 $$

Answer 2

Consider the ring of polynomials modulo $\sum_{i < m} x^i$. As $\sum_{i < m} x^i$ divides $x^m - 1$, we have in this ring that $x^m = 1$, and thus, more generally, that $x^{p}$ depends only on the remainder of $p$ modulo $m$. In this way, we can reduce any polynomial modulo $\sum_{i < m} x^i$ to a polynomial of degree $\lt m$ (i.e., degree $\leq$ that of $\sum_{i < m} x^i$ itself). And, of course, the only polynomials of such degree which are divisible by $\sum_{i < m} x^i$ are its scalar multiples.

Thus, we find that a general polynomial $\sum_{i} a_i x^i$ is divisible by $\sum_{i < m} x^i$ if and only if $\sum_{i \in C} a_{i}$ is equal for each choice of residue class $C$ modulo $m$.

All the observations in the question for $m > 1$ are special cases of this (keeping in mind that $\Phi_m(x)$ divides $\sum_{i < m} x^i$ for $m > 1$). The remaining observation is that $x - 1$ divides $x^{k + 1} - 1$, which is trivial (by explicit calculation or by considering in the same way as above that $x = 1$ in the ring of polynomials modulo $x - 1$, and thus $\sum_{i} a_i x^i$ is divisible by $x - 1$ just in case $\sum_i a_i = 0$).