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 ?
On
Since the LHS is $(x-w)^{2}(x-w^{2})^{2}$ where $w = e^{2\pi i /3}$, we need to find $n$ such that $P(w) = P(w^{2}) = 0$ and $P'(w) = P'(w^{2}) = 0$. You may use the identity $w^{2} + w + 1 = 0$ for this.
On
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.
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}$.