# Using roots of unity to factorize polynomials

Engel's Problem Solving Strategies has the following exercise (p.260 #28).

Show $$x^4 +x^3+x^2+x+1 \hspace{0.1cm}\big{|}\hspace{0.1cm}x^{44}+x^{33}+x^{22}+x^{11}+1$$.

I've been working through these problems and have seen the following strategy implemented quite a bit. Essentially it boils down to the following:

Let $$\omega^5=1$$ be a fifth root of unity excluding $$1$$; then any $$\omega$$ satisfying this equation is simultaneously a root for the polynomial $$x^4 +x^3+x^2+x+1$$ and $$x^{44}+x^{33}+x^{22}+x^{11}+1$$, so claim follows.

Here is my question. Is it true that for every value of $$n$$, the roots of unity $$\omega$$ satisfying $$\omega^n=1$$, excluding $$1$$, are exactly the roots of the polynomial $$\sum_{j=0}^{n-1}x^j$$ ? Or, e.g., only prime $$n$$? Thank you.

• Note: it’s $(x^n-1)/(x-1)$ – J. W. Tanner Aug 9 at 22:17
• It's easier to use modular arithmetic - see my answer (I can elaborate if need be). – Bill Dubuque Aug 9 at 22:53
• $\omega^n -1 =(\sum\limits_{j=0}^{n-1}\omega^j)(\omega -1)$. And $(\omega-1)\ne 0$. So $\sum\limits_{j=0}^{n-1}\omega^j=0$ – fleablood Aug 9 at 23:33

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.

• On rereading the question, I realize I misread it. I was answering something which wasn't being asked in the second part of my answer, which I believe is the primary cause of the confusion. As this second part was wrong, I'm leaving my answer deleted. Thank you for your time & patience discussing my answer with me. – John Omielan Aug 9 at 22:43
• @John actually the idea in your answer does work (generically) - see my answer. – Bill Dubuque Aug 9 at 23:01
• @BillDubuque Yes, I know my idea in my first paragraph works. The issue was with my second paragraph, which was trying to answer something which wasn't being asked (due to my misreading the question). – John Omielan Aug 9 at 23:05

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.

• Thank you for the cross-references – Sawyer R. Aug 10 at 16:37