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.

so we know has roots equal to the cube roots of 1, not including itself, which are

Any polynomial of the form is divisible by if both and (this is the polynomial remainder theorem).

This means

But since is a root to , it follows that

and since , we have so that

From here, notice that if for some integer , then

which is to say, is divisible by for all in the given range that are *not* multiples of 3, i.e. the integers and for .

Since 2005 = 668*3 + 1, it follows that there are integers such that .

Finally, .