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

Question

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 ?

Answer 1

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.

Answer 2

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} $$

Answer 3

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 $$

Answer 4

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}$.

Answer 5

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$$