Proof of polynomial divisibility without using complex numbers? My question is the same as polynomial of degree n and its divisor except I want a solution that does not make use of complex numbers 

Problem: Find all positive integers $n$ such that $x^2+x+1\mid (x+1)^n+x^n+1$

Using wolframalpha, I can see that a number of solutions work, such as $2,4,7$. I tried substituting various values of $x$ in and then working in specific mod cases, but this doesn't really seem to work because it only gives possible values, not 'actual' values. Polynomial long division here is also quite unwieldy...

You can use a form of polynomial modular arithmetic here, working modulo $x^2+x+1$
We have $x^2+x+1\equiv 0$ so that $x+1\equiv -x^2$
also $x^3+x^2+x\equiv 0$ so that $x^3\equiv -x^2-x\equiv 1$
So $p_n(x)=(x+1)^n+x^n+1\equiv (-1)^nx^{2n}+x^n+1$
Now since $x^3\equiv 1$ and you have a $(-1)^n$ there you can work modulo $6$, because extra multiples of $6$ in the powers change nothing.
We have $$p_0(x)\equiv 3$$ $$p_1(x)\equiv -x^2+x+1\equiv 2x+2$$$$p_2(x)\equiv x^4+x^2+1\equiv x+x^2+1\equiv 0$$$$p_3(x)\equiv -x^6+x^3+1\equiv 1$$$$p_4(x)\equiv x^8+x^4+1\equiv x^2+x+1\equiv 0$$$$p_5(x)=-x^{10}+x^5+1\equiv-x+x^2+1\equiv-2x$$
So the division works for $n\equiv 2,4 \bmod 6$ and you have the remainders on polynomial division for the other residue classes.

Note that because $x^2+x+1$ is an irreducible polynomial, this method is algebraically equivalent to replacing $x$ by a root of the equation $x^2+x+1$, but the computations all take place in a polynomial ring which isn't identified with any particular known ring or field.
