$\frac{[\text { Complex numbers help solve the problem }] }{\text { [ }}$ Derivative and multiple roots $]$

For which $n$ is the polynomial $(x+1)^{n}-x^{n}-1$ divisible by:
a) $x^{2}+x+1$
b) $\left(x^{2}+x+1\right)^{2}$
c) $\left(x^{2}+x+1\right)^{3}$?
Let $Q(x)=(x+1)^{n}-x^{n}-1, P(x)=x^{2}+x+1$, then $x+1 \equiv -x^{2}, x^{3} \equiv 1(\bmod P)$ (the comparison of polynomials is analogous to the comparison of numbers).

a) $Q(x) \equiv (-1)^{n} x^{2 n}-x^{n}+1(\bmod P)$. Let's consider all possible cases.

1) $n$ is a multiple of 3. Then $(-1)^{n} x^{2 n}-x^{n}-1 \equiv (-1)^{n}-2(\bmod P)$.
2) $n \equiv 1(\bmod 6)$. Then $(-1)^{n} x^{2 n}-x^{n}-1 \equiv -x^{2}-x-1 \equiv 0(\bmod P)$.
3) $n \equiv 2(\bmod 6)$. Then $(-1)^{n} x^{2 n}-x^{n}-1 \equiv x-x^{2}-1 \equiv 2 x(\bmod P)$.
4) $n \equiv 4(\bmod 6)$. Then $(-1)^{n} x^{2 n}-x^{n}-1 \equiv x^{2}-x-1 \equiv -2 x-2(\bmod P)$.
5) $n \equiv 5(\bmod 6)$. Then $(-1)^{n} x^{2 n}-x^{n}-1 \equiv -x-x^{2}-1 \equiv 0(\bmod P)$.

Thus, $Q$ is divisible by $P$ when $n \equiv 1,5(\bmod 6)$. In particular, $n$ is odd.

b) As in problem $\underline{61139}$, it is sufficient to check whether $Q^{\prime}$ is divisible by $P. Q^{\prime}(x)=n(x+1)^{n-1}-n x^{n-1} \equiv n\left(x^{2 n-2}-x^{n-1}\right)$ $(\bmod P)$.

When $n \equiv 1(\bmod 3) x^{2 n-2}-x^{n-1} \equiv 1-1=0(\bmod P)$.

When $n \equiv 2(\bmod 3) x^{2 n-2}-x^{n-1} \equiv x^{2}-x \equiv -2 x-1(\bmod P)$.

Thus, $Q$ is divisible by $P^{2}$ when $n \equiv 1(\bmod 6)$.

c) $Q^{\prime \prime}=n(n-1)\left((x+1)^{n-2}-x^{n-2}\right) \equiv -n(n-1)\left(x^{2 n-4}+x^{n-2}\right) \equiv -n(n-1)\left(x+x^{2}\right) \equiv n(n-1)(\bmod P)$.

Thus, $Q$ is divisible by $P^{3}$ only when $n=1$. Indeed, in this case, the polynomial $Q$ becomes zero.

## Answer

For a) $n=6 k \pm 1$;
b) $n=6 k+1$;
c) $n=1$.