## dividing $x^{2013}-1$

For students of class 11-12 (age 16+)
photon
Posts: 186
Joined: Sat Feb 05, 2011 3:39 pm
Location: dhaka
Contact:

### dividing $x^{2013}-1$

Find the remainder on dividing $x^{2013} - 1$ by $(x^2+1)(x^2+x+1)$ .
Try not to become a man of success but rather to become a man of value.-Albert Einstein

sowmitra
Posts: 155
Joined: Tue Mar 20, 2012 12:55 am

### Re: dividing $x^{2013}-1$

Let, $\mathcal{P}(x)=x^{2013}-1$. Also, suppose, when $\mathcal{P}(x)$ is divided by $(x^2+1)(x^2+x+1)$, the remainder is $\mathcal{R}(x)$. So, $\mathcal{R}(x)$ is a 3-Degree polynomial. [$\because (x^2+1)(x^2+x+1)$ is a 4-Degree polynomial.]
So, $\mathcal{P}(x)=(x^2+1)(x^2+x+1)\mathcal{Q}(x)+\mathcal{R}(x)$
$\therefore \mathcal{R}(x)=\mathcal{P}(x)-(x^2+1)(x^2+x+1)\mathcal{Q}(x)$

Now,
$\mathcal{R}(\omega)=\mathcal{P}(\omega)=0...(1)$,
$\mathcal{R}(i)=\mathcal{P}(i)=i-1...(2)$,
$\mathcal{R}(-i)=\mathcal{P}(-i)=-i-1...(3)$.
Here, $i^2=-1$, $\omega^3=1$ ($i,\omega \in \mathbb{C}$).

Let, $\mathcal{R}(x)=Ax^3+Bx^2+C$, where, $A$, $B$, $C$ are constants in $\mathbb{R}$.
$\therefore (1) \Rightarrow A+B \omega^2+C=0$
$\Rightarrow (A+C)+B \omega^2=0$
$\Rightarrow A+C=0$, &, $B=0$
Again,
$(2)\Rightarrow Ai^3+C=i-1\Rightarrow -Ai+C=i-1...(4)$
$(3)\Rightarrow A(-i)^3+C=-i-1\Rightarrow Ai+C=-i-1...(5)$
Adding $(4)$ & $(5)$, we get, $2C=-2\Rightarrow C=-1$. So, $A=1$.

$\therefore$ the remainder, $\mathcal{R}(x)=1.x^3+0.x^2+(-1)=\boxed{x^3-1}$.
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

SMMamun
Posts: 57
Joined: Thu Jan 20, 2011 6:57 pm

### Re: dividing $x^{2013}-1$

@sowmitra,
A 3-degree polynomial should have the form:
$$Ax^3+Bx^2+Cx+D$$
Therefore the remainder cannot be right.

The error is also (consequently) evident if we put the value of $C=-1$ in equation $(4)$ or $(5)$ rather than in the equation $A+C=0$.

SMMamun
Posts: 57
Joined: Thu Jan 20, 2011 6:57 pm

### Re: dividing $x^{2013}-1$

Solution
Let the dividend $f(x)=x^{2013}-1$, when divided by the divisor $d(x)=(x^2+1)(x^2+x+1)$, give us the quotient $q(x)$ and the remainder $r(x)$.
Thus $f(x)=q(x)d(x)+r(x) ... ... ...(1)$

Since $d(x)$ is a 4-degree polynomial, $r(x)$ will, at best, be a 3-degree polynomial.
So, let $r(x)=ax^3+bx^2+cx+d$.
$(1)\Rightarrow f(x)=q(x)d(x)+r(x)$
$\Rightarrow x^{2013}-1=q(x)(x^2+1)(x^2+x+1)+(ax^3+bx^2+cx+d) ... ... ...(2)$

We need to determine the values of $a$, $b$, $c$, and $d$, and therefore need four simultaneous equations involving the parameters. The major problem is that $q(x)$ is a big unknown here. The trick is to factorize $d(x)$, and see which values for $x$ make $d(x)=0$ and thus eliminate $q(x)d(x)$.

$(2)\Rightarrow x^{2013}-1=q(x)(x-i)(x+i)(x-\omega)(x-\omega^2 )+(ax^3+bx^2+cx+d) ... ... ...(3)$,
in which $i$ is the imaginary square root and $ω$, $ω^2$ are the imaginary cube roots of unity.

Now putting $x=i,-i,ω,ω^2$ in $(3)$, we get the required four equations, which, if solved, provide us the following values: $a=1, b=2, c=2, d=1$.

The remainder is therefore $x^3+2x^2+2x+1$.

A slightly different approach
If for a set of different $x$ values, we get a corresponding set of $r(x)$ values, we can directly apply Lagrange Interpolation to determine the expression $r(x)$ as a polynomial, whose degree will be 1 less than the available data points. In this approach, we no longer need to develop or solve the four equations. However, it is a laborious task to manually simplify the Lagrange Interpolation Polynomial expression when you have a number of data points.

Limitations
The two methods are not sufficient if you have repeated factors in $d(x)$. Think why!

sowmitra
Posts: 155
Joined: Tue Mar 20, 2012 12:55 am

### Re: dividing $x^{2013}-1$

Sorry...
"Rhythm is mathematics of the sub-conscious."
Some-Angle Related Problems;

mutasimmim
Posts: 107
Joined: Sun Dec 12, 2010 10:46 am

### Re: dividing $x^{2013}-1$

Brief solution sketch:
Note that $x^n-1$ is divisible by $(x^2+1)(x^2+x+1)$ if $n$ is divisible by $12$, and $2004$ is divisible by $12$.
Thus $x^{2013}-1=x^9(x^{2004}-1)+x^9-1\equiv x^9-1(mod (x^2+1)(x^2+x+1))$. Now it is easy to compute $x^9-1(mod (x^2+1)(x^2+x+1))$ by some written calculations.

*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

### Re: dividing $x^{2013}-1$

mutasimmim wrote:Now it is easy to compute $x^9-1(mod (x^2+1)(x^2+x+1))$ by some written calculations.
Or use modular arithmetic

$\dfrac{x^9-1}{x^2+x+1} \equiv (x-1)(x^6+x^3+1) \equiv x+1 \pmod{x^2+1}$
So, $x^9-1 \equiv (x+1)(x^2+x+1) \equiv {x^3+2x^2+2x+1}\pmod {(x^2+1)(x^2+x+1)}$
Use $L^AT_EX$, It makes our work a lot easier!