<s>[INST] Find $n$ such that polynomial is divisible Find $n \in N$, such that:
$$(x^2+x+1)^2 | x^n+(x+1)^n+1 = P(x)$$
If I let $Q(x) = x^2 + x + 1$, I have that $x^3 \equiv 1$ mod$Q(x)$, so I can work out the cases for remainder of $n$ when divided by $3$ ..
But what to do next, because I need $Q^2(x)$ dividing $P(x)$ ?
I suppose this could be done with complex zeroes, but is there a faster way ?
 [/INST] Since $(x^2+x+1)^2$ divides $P(x):=x^n+(x+1)^n+1$, we get that $Q(x):=x^2+x+1$ divides its derivative $P'(x)=n(x^{n-1}+(x+1)^{n-1})$.
Let us see when $n(x^{n-1}+(x+1)^{n-1})$ is divisible by $Q$ by working modulo $Q(x)$. Since $x^2+x+1=0$ we get $x^2=-(x+1)$ and
$$x^3=x^2x=-(x+1)x=-x^2-x=(x+1)-x=1,$$
hence
$$x^{3k}=1, x^{3k+1}=x, x^{3k+2}=x^2=-(x+1)$$
for all $k\in\mathbb{N}$, and similarly
$$(x+1)^k=(-1)^kx^{2k}.$$
Then we get
$$n(x^{3k}+(x+1)^{3k})=n(1+(-1)^{3k}),$$
so it is $0$ iff $k$ is odd, i.e., if $3k=6k'+3$,
and $$n(x^{3k+1}+(x+1)^{3k+1})=n(x+(-1)^{3k+1}x^2),$$
$$n(x^{3k+2}+(x+1)^{3k+2})=n(x^2+(-1)^{3k+2}x),$$
which can never be zero.
Hence $Q(x)^2$ divides $P(x)$ iff $n\equiv 4\pmod{6}$.
</s>