<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] Let's call your polynomial $P_n(x)$, to indicate the dependence on $n$.  If $\omega$ is a root of $x^2 + x + 1$, we want 
$\omega$ to be a root of $P_n(x)$ of multiplicity $\ge 2$,
which means both $P_n(\omega) = \omega^n + (\omega+1)^n + 1 = 0$ and
$P_n'(\omega) = n \omega^{n-1} + n (\omega+1)^{n-1} = 0$.  This last
simplifies to $$\left(1 + \frac{1}{\omega}\right)^{n-1} = -1$$
Now if $\omega^2 + \omega+1 = 0$ we have $\omega + 1 + 1/\omega = 0$, i.e. $1+1/\omega = -\omega$.  Since the powers of $\omega$ repeat $1, \omega, \omega^2$, we see that this is true if and only if $n-1 \equiv 3 \mod 6$, i.e. $n \equiv 4 \mod 6$.  For such $n$ we also have 
$P_n(\omega) = \omega^n + (-\omega^2)^n + 1 = \omega + \omega^2 + 1 = 0$, so both conditions are true.
</s>