Divisibility of a polynomial by another polynomial I have this question: 
Find all numbers $n\geq 1$ for which the polynomial $x^{n+1}+x^n+1$ is divisible by $x^2-x+1$. How do I even begin?
So far I have that  $x^{n+1}+x^n+1 = x^{n-1}(x^2-x+1)+2x^n-x^{n-1}+1,$ and so the problem is equivalent to finding $n$ such that  $2x^n-x^{n-1}+1$ is divisible by $x^2-x+1.$
A solution that I found goes as follows (but I don't understand it!):
Assume that $x^n+1=(x^m-x+1)Q(x).$ The polynomial $x^m-x+1$ has a real root in the interval $(0,1)$ but $x^n+1$ has no positive real roots. So, no such pairs $m,n$ exist.
Any help?
 A: Let $\omega = e^{\frac{i\pi}{3}}$, then $\omega^2 - \omega  + 1 = 0$.
If there is a $n$ such that $x^2 - x + 1 $ divides $P_n(x) = x^{n+1} + x^n + 1$, then 
$$ 0 = P_n(\omega) = \omega^n(\omega+1)+1.$$
$$ \omega^n(\omega+1) = -1.$$
$\omega+1 = \sqrt{3}e^{\frac{i\pi}{6}}$ is a vector of length $\sqrt{3}$. After a rotation it becomes $-1$, a vector of length $1$.
This is absurd.
A: Hint: The roots of $x^2-x+1=0$ are $e^{i\pi/3}$ and $e^{-i\pi/3}$. If we show that one (and therefore the other) cannot be a root of $x^{n+1}+x^n+1$, then we will know that $x^2-x+1$ cannot divide $x^{n+1}+x^n+1$. 
There are $3$ cases to examine: (i) $n$ is of the form $3k+2$; (ii) $n$ is of the form $3k+1$; and (iii) $n$ is of the form $3k$.
A: Alas, this is no lovely proof, but here goes: Computing coefficients by hand, we see:
$1 + x^n + x^{n+1}$
$=$
$(1-x+x^2)({\bf 1} + {\bf 1}x + {\bf 0}x^2 - {\bf 1}x^3 - {\bf 1}x^4 + {\bf 0}x^5 + {\bf 1}x^6 + {\bf 1}x^7 + {\bf 0}x^8 + \cdots)$
but
$x^{n+1} + x^n + 1$
$=$
$(x^2-x+1)({\bf 1}x^{n-1} + {\bf 2}x^{n-2} + \cdots)$
These sequences of coefficients do not agree.
EDIT in response to "How can we prove that?":
We prove it by spelling out a little more what we're doing by comparing the above sequences of coefficients.  Assume the polynomials divide evenly and write:
$1 + x^n + x^{n+1}$
$=$
$(1-x+x^2)(c_0 + c_1 x + c_2 x^2 + \cdots + c_{n-1}x^{n-1}) \quad.$
By induction we can show that $\ c\ $ is the sequence $\ \langle 1,1,0,-1,-1,0,1,1,0,\dots\rangle\ $.
The base cases are $\ c_0 = 1\ $ and $\ c_1 = 1\ .\ $For the induction step, we see there is a recurrence relation $\ 0 = c_i - c_{i-1} + c_{i-2}\ $ for $\ 2 \leq i \leq n-1\ .\ $(All proofs come from multiplying out the second line and comparing coefficients with $\ 1 + x^n + x^{n+1}\ .)\ $This recurrence relation yields the sequence given above.
But then $\ c_{n-2}\ $ is either $\ -1\ $, $\ 0\ ,\ $or $\ 1\ .\ $In particular, it is not $\ 2\ ,\ $in contradiction to what we find computing coefficients in the opposite direction.
Is this proof sketch more clear?
