Remainder when $x^{2016}+x^{2013}+\cdots+x^6+x^3$ is divided by $x^2+x+1$.

Question

I am currently preparing for a certain quiz show when I encountered this question:

What is the remainder when $x^{2016}+x^{2013}+\cdots+x^6+x^3$ is divided by $x^2+x+1$?

I know for a fact that $x^3-1=(x-1)(x^2+x+1)$.

And I got

$$x^{2016}+x^{2013}+\cdots+x^6+x^3=x^3(x^{2013}+x^{2010}+\cdots+x^3+1)$$ $$=[(x-1)(x^2+x+1)+1](x^{2013}+x^{2010}+\cdots+x^3+1)$$ $$=(x-1)(x^2+x+1) (x^{2013}+x^{2010}+\cdots+x^3+1)+(x^{2013}+x^{2010}+\cdots+x^3+1)$$

I know that the remainder comes from the term not containing $x^2+x+1$ but I do not know to get it since it involved so many terms.

Any help please? Thanks in advanced!

Answer 1

As $x^3=1\implies x^{3n}=(x^3)^n=1\implies x^{3n}\equiv1\pmod{x^2+x+1}$

and $2016=3\cdot672$

$$\sum_{r=1}^{672}x^{3r}\equiv\sum_{r=1}^{672}1\pmod{x^2+x+1}$$

Answer 2

\begin{align} \sum_{k=1}^{672}x^{3k}&=\sum_{k=1}^{672}\left((x-1)(x^2+x+1)+1\right)^{k}\\ &=\sum_{k=1}^{672}\left(\sum_{j=0}^{k}{k \choose j}\left((x-1)(x^2+x+1)\right)^{j}\right)\\ &=\sum_{k=1}^{672}\left((x^2+x+1)P_k(x)+1\right)\\ &=(x^2+x+1)P(x)+\sum_{k=1}^{672}1 \end{align}