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
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}$.
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}$.
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$.
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$.
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!
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!
Re: dividing $x^{2013}-1$
Sorry...
-
- 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.
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.
Re: dividing $x^{2013}-1$
Or use modular arithmeticmutasimmim wrote:Now it is easy to compute $x^9-1(mod (x^2+1)(x^2+x+1))$ by some written calculations.
$\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)}$
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
-
- Posts:107
- Joined:Sun Dec 12, 2010 10:46 am
Re: dividing $x^{2013}-1$
Well, that's new!Or use modular arithmetic