Algo-3

As per the other solutions, complex numbers look to be the right way to go, but in an effort to solve without them we can note that if $p(x)$ is divisible in the polynomial sense by $x^2+x+1$ , then $x^2+x+1$ will also divide $p(x)$ for all integers $x$ . (A simple comparison of coefficients shows that if the quotient is a polynomial, it would have to have integer coefficients.)

Consider the case $x=2$ , and let $k=3n$ . We have $x^2+x+1=7$ , and $p(2)=2^{6n}+1+3^{6n} = 64^n+729^n+1$ .

Reducing modulo $7$ , we find $p(2) \equiv 3$ , since both $64$ and $729$ are congruent to $1$ modulo $7$ .

This is enough to prove that $p(x)$ is never divisible by $x^2+x+1$ when $k=3n$ (so it's enough to answer this form of the question, as it's multiple choice). Proving that these are the only such $k$ is harder by this method.

Similar solution as @Alak Bhattacharya 's

The roots to $x^2+x+1 = 0$ is the complex cubic root of unity $\omega$ . This is because, if we multiply both sides by $x$ and $+1$ , we have $x^3 + \blue{x^2 + x + 1} = 1 \implies x^3 + \blue 0 = 1 \implies \omega^3 = 1$ . Then we have:

$\omega^n = \begin{cases} 1 & \text{if }n \bmod 3 = 0 \\ \omega & \text{if }n \bmod 3 = 1 \\ \omega^2 & \text{if }n \bmod 3 = 2 \end{cases}$

We note that $p(x)$ is divisible by $x^2+x+1$ , when $p(\omega) = 0$ . Let us consider $p(\omega)$ .

$\begin{aligned} p(\omega) & = \omega^{2k} + 1 + (\blue{\omega + 1})^{2k} & \small \blue{\text{As }\omega^2 + \omega + 1 = 0} \\ & = \omega^{2k} + 1 + (\blue{-\omega^2})^{2k} \\ & = \omega^{2k} + 1 + \omega^{\blue{4k}} & \small \blue{\text{and }\omega^{(3+1)k} = \omega^k} \\ & = \omega^{2k} + \omega^{\blue k} + 1 \\ & = \begin{cases} 3 & \text{if }k \bmod 3 = 0 \\ 0 & \text{if }k \bmod 3 = 1 \\ 0 & \text{if }k \bmod 3 = 2 \end{cases} \end{aligned}$

Therefore, $p(x)$ is not divisible by $x^2+x+1$ or $p(\omega) \ne 0$ , when $k = \boxed{3n}$ , where $n$ is a natural number.

If $p(x)$ be not divisible by $x^2+x+1$ , then $p(\omega) \neq 0$ , where $\omega$ is a complex cube root of unity (i.e., a root of the equation $x^2+x+1=0$ ). This means

$\omega^{2k}+1+(-\omega) ^k\neq 0$ . This is true for $k=\boxed {3n}$ where $n$ is a natural number.