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=(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\\eq0`

`\omega^(4(3k))+\omega^(2(3k))+1=1+1+1=3\\eq0`

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}`.