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?
 A: 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 $$
A: 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$).
