How can I show that $1+x+...+x^{n-1}$ divides any polynomial with distinct exponents mod n?

Question

Given a polynomial $f(x) = x^{a_1}+x^{a_2}+...+x^{a_n}$, where each $a_j\equiv j - 1$ mod $n$, how can I show that $1+x+...+x^{n-1}$ divides $f(x)$?

So far, I've noted that any root of unity $\zeta_n$ is also a root of $(x-1)f(x)$. This means that the n-th cyclotomic polynomial $\Phi_n(x)$ divides $(x-1)f(x)$. The case where $n=1$ is trivial, and both $(x-1)$ and $\Phi_n(x)$ are irreducible, so $\Phi_n(x)|f(x)$.

I am not sure where to go from here; actually, I can't see any way to go on from here, so maybe I am taking entirely the wrong approach?

Answer 1

Note that $f = 1 + x + \cdots + x^{n - 1}$ divides $x^n - 1$ so when you reduce a polynomial by $f$ you can replace $x^m$ with $x^{m - n}$, i.e., you can reduce the exponents of $x$ modulo $n$.

Polynomials with distinct exponents modulo $n$ will therefore reduce to $f$ modulo $g$, hence reduce to $0$ modulo $f$.

Answer 2

$f(x)=x^{nk_1}+x^{nk_2+1}+x^{nk_3+2}+....+x^{nk_n+(n-1)}$

Now, $l(x)=1+x+x^2+x^3+....+x^{n-1}=\frac{x^n-1}{x-1}$.

So, if $l(x)|f(x)$ then ${x^n-1}|(x-1)f(x)$.

Now, $(x-1)f(x)= x^{n(k_1+1)+1}+x^{nk_2+2}+....+x^{n(k_n+1)} - (x^{nk_1}+x^{nk_2+1}+x^{nk_3+2}+....x^{nk_n+(n-1)})$

or, $(x-1)f(x)=(x^{nk_1+1}-x^{nk_2+1})+(x^{nk_2+2}-x^{nk_3+3})+......+(x^{nk_n+n}-x^{nk_1})$

or, $(x-1)f(x)=±x^{a_1n+1}(x^{m_1n}-1)±x^{a_2n+2}(x^{m_2n}-1)±.....±x^{a_nn+n}(x^{m_nn}-1)$

(where $a_i=\text{min}(k_i, k_{I+1})$)

So, $x^n-1|(x-1)f(x)$ and that implies $1+x+x^2+....+x^n=\frac{x^n-1}{x-1}|f(x)$.