Using roots of unity to factorize polynomials

Since $x^n-1=(x-1)(x^{n-1}+\cdots+x+1)$ the roots of $x^{n-1}+\cdots+x+1$ are precisely the $n$th roots of unity except for $x=1$. Note the roots are simple (have multiplicity $1$). So indeed it suffices to check that any root $\omega\ne 1$ of $\omega^5=1$ satisfies $\omega^{44}+\omega^{33}+\omega^{22}+\omega^{11}+1=0$, which can be checked by reducing the exponents mod $5$.

Moreover, the quotient $(x^{44}+x^{33}+x^{22}+x^{11}+1)/(x^4+x^3+x^2+x+1)$ is

$$ \left(\frac{x^{55}-1}{x^{11}-1}\right)/\left(\frac{x^5-1}{x-1}\right)=\frac{(x^{55}-1)(x-1)}{(x^{11}-1)(x^5-1)}=\Phi_{55}(x), $$

a cyclotomic polynomial, an instance of the formula $\Phi_d(x)=\prod_{d\mid n}(x^d-1)^{\mu(n/d)}$ which follows from applying Mobius inversion (multiplicatively) to $x^n-1=\prod_{d\mid n}\Phi_d(x)$ from Galois theory.


Yes, $\,0 = w^n\!-1 = (w\!-\!1)f(w)\ $ so $\ w\!-\!1\neq 0\,\Rightarrow\, f(w) = 0.\,$ More simply and generally:

$\!\begin{align}{\bf Theorem}\ \ f(x):= x^{\large 4}\!+\!x^{\large 3}\!+\! x^{\large 2}\!+\!x\!+\!1\,&\mid\, x^A\! +\! x^B\! +\! x^C\! +\! x^D\! +\! x^E\\[.3em] {\rm if} \ \ \ \{4,\ 3,\ 2,\ 1,\ 0\}\ &\!\equiv\ \{A,\ B,\ C,\ D,\ E\} \pmod{\!5}\end{align}$

$\begin{align}{\bf Proof}\ \bmod f(x):\,\ \color{#c00}{x^{\large 5}\equiv 1}\,\Rightarrow\ &x^{\large j+5k}\equiv x^j(\color{#c00}{x^{\large 5}})^{\large k}\equiv x^{\large j}\ \ \ \rm therefore\\[.3em] & x^{\large 4+5i} + x^{\large 3+5j} + x^{\large 2+5k} + x^{\large 1+5\ell} + x^{\large 5m}\\[.3em] \equiv\ & x^{\large 4} + x^{\large 3} + x^{\large 2} + x + 1\\[.3em] \equiv\ & f(x) \equiv\ 0 \end{align}$

See this answer for the general idea, and here for a more general "simpler multiple" perspective, which proves very handy for Problem Solving Strategies.