<s>[INST] Spotting that $\,x^8 + x^7 + 1\,$ is reducible. 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?
 [/INST] 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 $$
</s>