$6 \cdot 25$ Find all positive integers $k$ such that the polynomial $x^{2 k+1}+x+1$ is divisible by $x^{k}+x+1$. For each $k$ that satisfies this condition, find all positive integers $n$ such that $x^{n}+x+1$ is divisible by $x^{k}+x+1$.
(British Mathematical Olympiad, 1991)
[Solution] Since $x^{k}+x+1 \mid x^{2 k+1}+x+1$,
then
$$
x^{k}+x+1 \mid \left(x^{2 k+1}+x+1\right)-\left(x^{k}+x+1\right) \text {, }
$$

which means
$$
x^{k}+x+1 \mid x^{k}\left(x^{k+1}-1\right) \text {. }
$$

Since
$$
x+1 \mid x^{k}-(-1)^{k} \text {, }
$$

we have
$$
\begin{array}{c}
\left(x^{k}, x+1\right)=1 \\
\left(x^{k}, x^{k}+x+1\right)=\left(x^{k}, x+1\right)=1 .
\end{array}
$$

Thus, $x^{k}$ and $x^{k}+x+1$ are coprime.
By (1), we must have
$$
x^{k}+x+1 \mid x^{k+1}-1
$$

Also, $\quad x^{k+1}-1=x\left(x^{k}+x+1\right)-\left(x^{2}+x+1\right)$,
so
$$
x^{k}+x+1 \mid x^{2}+x+1 \text {, }
$$

Therefore,
$$
k=1 \text { or } 2 \text {. }
$$

But when $k=1$,
$$
x^{k}+x+1=2 x+1 \nmid x^{2}+x+1 \text {, }
$$

so
$$
k=2 \text {. }
$$

Since the roots of $x^{2}+x+1$ are $\quad \omega=\frac{-1 \pm \sqrt{3} i}{2}$
where $i$ is the imaginary unit, i.e., $i^{2}=-1$.
If $x^{n}+x+1$ can be divided by $x^{2}+x+1$, then
$$
\omega^{n}+\omega+1=0 .
$$

Thus, $n=3 m+2$, where $m$ is a non-negative integer.