Question

Let $m$ be the number of integers $n$, $1 \le n \le 2005$, such that the polynomial $x^{2n} + 1 + (x + 1)^{2n}$ is divisible by $x^2 + x + 1$. Find the remainder when $m$ is divided by 1000.

Answer 1

$x^2+x+1=\dfrac{x^3-1}{x-1}$

so we know $x^2+x+1$ has roots equal to the cube roots of 1, not including $x=1$ itself, which are

$\omega=e^{2i\pi/3}\text{ and }\omega^2=e^{4i\pi/3}$

Any polynomial of the form $p_n(x)=x^{2n}+1+(x+1)^{2n}$ is divisible by $x^2+x+1$ if both $p(\omega)=0$ and $p(\omega^2)=0$ (this is the polynomial remainder theorem).

This means

$p(\omega)=\omega^{2n}+1+(1+\omega)^{2n}=0$

But since $\omega$ is a root to $x^2+x+1$, it follows that

$\omega^2+\omega+1=0\implies1+\omega=-\omega^2$

$\implies\omega^{2n}+1+(-\omega^2)^{2n}=0$

$\implies\omega^{4n}+\omega^{2n}+1=0$

and since $\omega^3=1$, we have $\omega^{4n}=\omega^{3n}\omega^n=\omega^n$ so that

$\implies\omega^{2n}+\omega^n+1=0$

From here, notice that if $n=3k$ for some integer $k$, then

$\omega^{2(3k)}+\omega^{3k}+1=1+1+1=3\neq0$

$\omega^{4(3k)}+\omega^{2(3k)}+1=1+1+1=3\neq0$

which is to say, $p(x)$ is divisible by $x^2+x+1$ for all $n$ in the given range that are *not* multiples of 3, i.e. the integers $3k-2$ and $3k-1$ for $k\ge1$.

Since 2005 = 668*3 + 1, it follows that there are $m=668 + 669 = 1337$ integers $n$ such that $x^2+x+1\mid p(x)$.

Finally, $m\equiv\boxed{337}\pmod{1000}$.