# Find remainder of division of $x^3$ by $x^2-x+1$ [duplicate]

I am stuck at my exam practice here.

The remainder of the division of $$x^3$$ by $$x^2-x+1$$ is ..... and that of $$x^{2007}$$ by $$x^2-x+1$$ is .....

I tried the polynomial remainder theorem but I am not sure if I did it correctly.

By factor theorem definition, provided by Wikipedia,

the remainder of the division of a polynomial $$f(x)$$ by a linear polynomial $$x-r$$ is equal to $$f(r)$$.

So I attempted to find $$r$$ by factorizing $$x^2-x+1$$ first but I got the complex form $$x=\frac{1\pm\sqrt{3}i}{2}=r$$.

$$f(r)$$ is then $$(\frac{1+\sqrt{3}i}{2})^3$$ or $$(\frac{1-\sqrt{3}i}{2})^3$$ which do not sound right.

However, the answer key provided is $$-1$$ for the first question and also $$-1$$ for the second one. Please help.

• math.stackexchange.com/questions/3266201/… – lab bhattacharjee Jun 18 '19 at 15:12
• Why is my method using the remainder theorem $f(r)$ faulty though? – Trey Anupong Jun 18 '19 at 15:18
• Just to nitpick, what you provided there does not follow by definition, but rather, by the factor theorem. The definition of the remainder of $p/q$ is the polynomial $r$ such that $$\tfrac{p}{q}=s + \tfrac{r}{q},$$ where $s$ is polynomial and $\deg(r) < \deg(q)$. – Luke Collins Jun 18 '19 at 15:21
• @LukeCollins thank you for pointing that out, edited done! – Trey Anupong Jun 18 '19 at 15:29
• @TreyAnupong Then better to start with the 3rd link – Bill Dubuque Jun 18 '19 at 16:39

Since $$x^3+1 = (x+1)(x^2-x+1)$$ so $$x^3 = (x+1)(x^2-x+1)-1$$ the answer is $$-1$$.

Similarly for $$\begin{eqnarray}x^{3n}+1 &=& (x^3+1)\underbrace{\Big((x^3)^{n-1}-(x^3)^{n-2}+...-(x^3)+1\Big)}_{q(x)}\\ &=& (x+1)(x^2-x+1)q(x)\\ \end{eqnarray}$$

so the answer is again $$-1$$.

Another way if you're familiar with modular arithmetic is to work modulo $$x^2-x+1$$, in which case we have $$x^2\equiv x-1$$ and thus $$x^3\equiv xx^2\equiv x(x-1)\equiv x^2-x\equiv (x-1)-x\equiv -1.$$ This can be extended to your other question by noting that $$x^{2007}=\left(x^3\right)^{669}$$.

One way of writing this is to borrow the notion of equivalence (encoded in the notion of Ideals etc)

Because $$x^3+1=(x+1)(x^2-x+1)$$, we can write $$x^3\equiv -1 \bmod (x^2-x+1)$$

Then $$x^{2007}=(x^3)^{669}\equiv (-1)^{669}$$

This can be a surprisingly effective and efficient way of doing these questions about polynomial division and remainders.

(1) Since $$x^3=(x^3+1)-1=(x+1)(x^2-x+1)-1$$, the remainder is $$-1$$.

(2) $$\displaystyle x^{2007}=(x^3)^{669}=[(x+1)(x^2-x+1)-1]^{669}=-1+\sum_{k=1}^{669}(x+1)^k(x^2-x+1)^k(-1)^{669-k}$$

The remainder is $$-1$$.