Remainder of $(1+x)^{2015}$ after division with $x^2+x+1$ 
Remainder of $(1+x)^{2015}$ after division with $x^2+x+1$

Is it correct if I consider the polynomial modulo $5$
$$(1+x)^{2015}=\sum\binom{2015}{n}x^n=1+2015x+2015\cdot1007x^2+\cdots+x^{2015}$$
RHS stays the same and then The remainder must be of the form $Ax+B$
$$x^{2015}+1\equiv Ax+B\pmod{1+x+x^2}$$
plug in $x=0\implies B=0$
plug in $x=1\implies A=-1\implies $ the remainder is $-x$
Is this a good way to solve the problem or were we lucky ?
 A: First, your arithmetic is wrong - you should get $x=0\implies B=1$ from the equation you are using.
Second your method is wrong. If you want to use the modulus you have $$(1+x)^{2015}=Q(x)(x^2+x+1) +Ax+B$$
If you set $x=0$ you get $1=Q(0)+B$ and since you don't know anything about $Q(x)$ yet, this tells you nothing useful.
If, however, you were to choose $x=\omega$ where $\omega^2+\omega+1=0$ and $\omega^3=1$ you would find that $$(1+\omega)^{2015}=A\omega+B$$And you would have $1+\omega=-\omega^2$ so that $(1+\omega)^{2015}=-\omega^{4030}$
And you can go on from there to solve the problem.
A: use the division algorithm to write $$(1 + x)^{2015} = q(x)(x^2 + x+ 1)+ax + b\tag 1$$  the  roots of $x^2 + x+ 1 = 0$ are $\omega = e^{i2\pi/3}, \bar {\omega}.$  we need $$1 + \omega = e^{i\pi/3},1 + \bar \omega = e^{-i\pi/3}  $$  subbing $e^{i\pi/3}, e^{-i\pi/3}$ in $(1)$  gives us $$e^{\pm i2015\pi/3} = ae^{\pm i\pi/3} + b\to e^{\mp i\pi/3} = ae^{\pm 2i\pi/3} + b$$
gives you $$ a = -1, b = 0, \text{ the remainder is } -x $$
A: Method $\#1:$
Observe that $$1+x\equiv-x^2\pmod{x^2+x+1}\text{  and }x^3\equiv1$$
$$\implies(1+x)^{3n+2}\equiv(-x^2)^{3n+2}\equiv(-1)^{3n+2}(x^3)^{2n+1}\cdot x\equiv(-1)^nx$$  as $3n+2\equiv n\pmod2$
Method $\#2:$
Observe that $$(1+x)^2\equiv x\pmod{x^2+x+1}\text{  and }x^3\equiv1$$
$$\implies(1+x)^{6n+5}=\{(1+x)^2\}^{3n+2}\cdot(1+x)\pmod{x^2+x+1}$$
$$\equiv x^{3n+2}\cdot(x+1)$$
$$\equiv(x^3)^n\cdot x^2(x+1)$$
$$\equiv1^n\cdot(x^3+x^2)$$
$$\equiv1+x^2\equiv-x$$
A: Recall that $x^2+x+1=\Phi_3(x)$. If we set $\omega=\exp\left(\frac{2\pi i}{3}\right),\bar\omega=\left(\frac{2\pi i}{3}\right)$, we must have:
$$ (1+x)^{2015} = q(x)\cdot \Phi_3(x)+(Ax+B), \tag{1}$$
and evaluating the previous identity for $x\in\{\omega,\bar{\omega}\}$ we get:
$$ (1+\omega)^{2015} = A\omega+B,\quad (1+\bar\omega)^{2015} = A\bar\omega+B\tag{2}$$
but since $1+\omega=\exp\left(\frac{2\pi i}{6}\right)$ and $2015\equiv 5\pmod 6$, by setting $\zeta=\exp\left(\frac{2\pi i}{6}\right)$ we have that $(2)$ translates into:
$$ A\zeta^2 + B = \zeta^5,\quad A\zeta^4 + B = \zeta,\tag{3} $$
hence by Cramer's rule:
$$ A = \frac{\zeta^5-\zeta}{\zeta^2-\zeta^4}=-1, \qquad B=\frac{\zeta^3-\zeta^9}{\zeta^2-\zeta^4}=0.\tag{4} $$
A: Similar to Mark's answer, you can first change variable $t=x+1$ and that turns the problem to finding $t^{2015}\pmod{1-t+t^2}$. Now one can just use $t^3=1$ to reduce $t^{2015}$ to $t^2=t-1\pmod{1-t+t^2}$.
