Polynomial remainders I was trying some problems from this problem seminar worksheet and I was unable to make much progress on this particular problem. 
Find the remainder when $(x+2)^{2011} - (x+1)^{2011}$ is divided by $x^2+x+1$
 A: Hint:
One approach would be an analogue to what you do when reducing in modular arithmetic.
If, say, you were computing $5^{2011}-4^{2011}\pmod{31}$, you might first rewrite $r^{2011}=5\cdot 5^{2010}=5\cdot 5^{3\cdot 670}=5\cdot(125)^{670}$ and reduce $125$ using $31$, then repeat this process.
So in this case, you might try $(x+2)^{2011}\\=(x+2)(x+2)^{2\cdot 1005}\\=(x+2)(x^2+4x+4)^{1005}\\\equiv(x+2)(3x+3)^{1005}\pmod{x^2+x+1})$
Then you could repeat the same process on $(3x+3)^{1005}=(3x+3)(9x^2+18x+9)^{502}\equiv(3x+3)(9x)^{502}$
There are also probably smarter ways to reduce the expression more quickly by noticing a clever factorization.
A: One way to do this is to recognize that you’re working in $\mathbb Z[x]/(x^2+x+1)\cong \mathbb Z[\omega]$, where $\omega$ is a primitive cube root of unity, say $\omega=(-1+\sqrt{-3}\,)/2$.
Then $x+1$ represents $\omega+1=-\omega^2$, a primitive sixth root of unity. Now we look at $\omega+2=(3+\sqrt{-3}\,)/2=\sqrt{-3}\,(1-\sqrt{-3}\,)/2=\sqrt{-3}(-\omega)$, where you see that $-\omega$ is also a sixth root of unity.
Now we use the fact that $2011\equiv1\pmod6$ to get rid of the high powers on $\omega$ and $-\omega$, to see that $(x+1)^{2011}$ is represented by $-\omega$, in other words is congruent to $x+1$ modulo $x^2+x+1$. And the story for $(x+2)^{2011}$ is only a little more complicated. It’s represented by $(-3)^{1005}(x+2)$, if you don’t mind my skipping a few steps.
Thus the final result is that
$$
(x+2)^{2011} - (x+1)^{2001}\quad\equiv\quad-[1+3^{1005}]\,x\>+\> -[1+2\cdot3^{1005}]\pmod{x^2+x+1}
$$
