How to approach this divisibility problem on polynomial Prove that the polynomial $x^{9999} + x^{8888} + x^{7777} + ... + x^{1111} + 1$ is divisible by $x^9 + x^8 + x^7 + ... + x + 1$.
I have no idea how to approach this problem, some help would be appreciated.
 A: Let $f(x)=x^{9999}+x^{8888}+x^{7777}+\cdots+x^{1111}+1$ and $g(x)=x^9+x^8+x^7+\cdots+x+1$.
If $g(\alpha)=0$, then $\alpha^{10}=(\alpha-1)g(\alpha)+1=1$.
So, $f(\alpha)=\alpha^{9999}+\alpha^{8888}+\alpha^{7777}+\cdots+\alpha^{1111}+1=\alpha^9+\alpha^8+\alpha^7+\cdots+\alpha+1=0$.
$f(x)$ is divisible by $x-\alpha$ for all $\alpha$ such that $g(\alpha)=0$.
If $\alpha$ is a repeated root of $g(x)=0$, then $g(\alpha)=g'(\alpha)=0$.
Since $g(x)(x-1)=x^{10}-1$, $g'(\alpha)(\alpha-1)+g(\alpha)=10\alpha^{9}$ and hence $\alpha=0$.
However, $g(0)\ne0$.
$g(x)$ has no repeated root.
$f(x)$ is divisible by $g(x)$.
A: Call it $\, f \div g.\ $ Note $\,\color{#c00}{x^{\large 10}\equiv 1}\pmod{\!g}\,$ by $\,x^{\large 10}\!-1 = (x\!-\!1)g,\,$ so
$\!\bmod g\!:\ x^{\large r+10q}\equiv x^{\large r}(\color{#c00}{x^{\large 10}})^{\large q}\equiv x^{\large r}\,\Rightarrow\, f\equiv g\equiv 0,\ $ so $\ g\mid f$.
A: $$ ( x^9 + x^8 + \ldots + x + 1) \left(x^{9990} - x^{9989} \right) =  x^{9999} - x^{9989}$$
So,
$$ x^{9999} - x^{9979} = x^{9999} - x^{9989} + x^{9989} - x^{9979} =  ( x^9 + x^8 + \ldots + x + 1) \left(x^{9990} - x^{9989} + x^{9980} - x^{9979} \right) $$
Continuing in this way, we see that:
$$ x^9 + x^8 + \ldots + x + 1\ \vert\ x^{9999} - x^9, $$
$$ x^9 + x^8 + \ldots + x + 1\ \vert\ x^{8888} - x^8, $$
$$ \ldots$$
$$ x^9 + x^8 + \ldots + x + 1\ \vert\ x^{1111} - x^1, $$
$$ x^9 + x^8 + \ldots + x + 1\ \vert\ 1 - 1, $$
Therefore,
$$ x^9 + x^8 + \ldots + x + 1\ \vert\ x^{9999} - x^9 + x^{8888} - x^8 + \ldots + x^{1111} - x^1 + 1 - 1,\quad \text{ i.e.,} $$
$$ x^9 + x^8 + \ldots + x + 1\ \vert\ x^{9999} + x^{8888} + \ldots + x^{1111} + 1 - \left( x^9 + x^8 + \ldots + x + 1 \right) $$
$$ \implies x^9 + x^8 + \ldots + x + 1\ \vert\ x^{9999} + x^{8888} + \ldots + x^{1111} + 1.$$
A: $$
x^{9999}+x^{8888}+x^{7777}+...+x^{1111}+1
=\frac{x^{11110}-1}{x^{1111}-1}
=\frac{(x^{10})^{1111}-1}{x^{1111}-1}
=\frac{(x^{10}-1)p(x)}{x^{1111}-1}=\frac{(x^9+x^8+x^7+...+x+1)p(x)}{q(x)}
$$
So it is enough to show that $\gcd(x^{10}-1,x^{1111}-1)=x-1$. Let $w_k=e^{\frac{2\pi i k}{10}}$, $0\leq k\leq 9$. Then $w_k^{1111}-1=w_k-1=0$ iff $k=0$. So $x-w_k$ divides $x^{1111}-1$ iff $w_k=1$.
What's wrong here? You downvote!
