Divisibility of a polynomial by another polynomial

Question

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?

Answer 1

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.

Answer 2

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?

Answer 3

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$.