2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Why does $x=0$ imply $B=0$? $\endgroup$ – Quang Hoang May 31 '15 at 13:33
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ does it always follow from $-w=Aw+B$ that $A=-1,B=0$ ? $\endgroup$ – ketum May 31 '15 at 14:24
  • 1
    $\begingroup$ @ketum You can write that as $(1+A)\omega=-B$ and if you don't have $A=-1, B=0$ you would be able to write $\omega$ as $-B/(1+A)$, but $\omega$ is not a real number, so this cannot be. $\endgroup$ – Mark Bennet May 31 '15 at 15:15
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @ketum, the plus and minus on the sides have opposite sense. $\endgroup$ – abel May 31 '15 at 13:47
  • 1
    $\begingroup$ @ketum, i found the error. it is fixed now. $\endgroup$ – abel May 31 '15 at 13:49
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why the downvote? $\endgroup$ – Jack D'Aurizio May 31 '15 at 14:21
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.