# Find the remainder of the division of polynomials

$$x^{2007}$$ divided by $$x^2-x+1$$.

I consider to solve this problem, should I break the $$x^{2007}$$ to find the formula $$x^2-x+1$$?

• Why $2007$? Have you tried smaller values, like $x$, $x^2$, $x^3$, $x^4$ etc.? – Angina Seng Nov 25 '18 at 12:55

Write: $$\boxed{x^{2007} = k(x)(x^2-x+1)+r(x)}$$ where $$r(x)$$ is a linear polynomial.

Say $$a$$ is zero of $$x^2-x+1$$, then $$a^2-a+1=0\;\;\;/\cdot (a+1)$$ we get $$a^3+1 =0 \;\;\Longrightarrow \;\;a^3 = -1$$ and if we put $$x=a$$ in boxed equation we get $$-1= a^{2007} = k(a)\cdot 0+r(a)$$ and the same for other zero $$b =\overline{a}$$.

So if $$r(x) = kx+n$$, then we have a system $$-1=ka+n$$ $$-1=kb+n$$ which can easly be solved.

• hmmm I still a little bit confused,, how can u know that a^3=-1? – Aster Zen Nov 25 '18 at 13:05
• If $a^2-a+1=0$ then if you multiply this with $a+1$ you get $a^3+1=0$ – Aqua Nov 25 '18 at 13:06
• can I break down the x^2-x+1 to x(x-1)+1 that the factor is x=0 and x=1, then I take them to ax+b so b=0 and a+b=1, and a=1 so the remainder is 1 ? but the answer is -1 :( – Aster Zen Nov 25 '18 at 13:07
• That is not correct. – Aqua Nov 25 '18 at 13:10
• oh yes I find the a^3=-1, so how can this and x+1 affect the equation ? I stil do not understand, is the equation become x^2007 = (a+1).0 + remainder ? – Aster Zen Nov 25 '18 at 13:15

Since various answers have already been given, here is another way of writing the same as has been suggested elsewhere.

This can be expressed in a form of modular arithmetic for polynomials. We have $$x^3+1=(x+1)(x^2-x+1)\equiv 0 \bmod (x^2-x+1)$$

Now taking equivalences to the same modulus we have $$x^3\equiv -1$$ and $$x^{2007}=x^{3\cdot669}=(x^3)^{669}\equiv (-1)^{669}\equiv -1$$

This seems to me to be surprisingly rarely used, but often has the same notational convenience as modular arithmetic for integers.

• is this the Fermat's little theorem ? – Aster Zen Nov 25 '18 at 13:42
• @AsterZen No. It reflects the fact that any individual polynomial generates what is called an "Ideal" in the Ring of all polynomials, and that factoring out the Ideal from the Ring (creating $R/I$) is a homomorphism of rings. This means that if you divide everything by your original polynomial and only bother with the remainders, the arithmetic works out [up to a multiple of the original polynomial]. The way we normally do modular arithmetic with integers also involves only looking at the remainders. – Mark Bennet Nov 25 '18 at 13:51

Doing long division: $$\frac{x^{2007}}{x^2-x+1}=\frac{x^{2008}+x^{2007}}{x^3+1}=\\ \frac{(x^3+1)(x^{2005}+x^{2004}-x^{2002}-x^{2001}+x^{1999}+x^{1998}-\cdots-x^4-x^3+x+1)-x-1}{x^3+1}=\\ a(x)-\frac{x+1}{x^3+1}=\\ a(x)+\frac{\color{red}{-1}}{x^2-x+1}.$$

• hmmm from where does the x^2008 come ? – Aster Zen Nov 26 '18 at 11:58
• it is $\frac{x^{2007}(x+1)}{(x+1)(x^2-x+1)}$ and it is easier to divide by binomial rather trinomial. – farruhota Nov 26 '18 at 12:08
• why we must multiple the polynomials by the (x+1) ? – Aster Zen Nov 26 '18 at 12:40
• multiply and divide by $(x+1)$ to simplify the denominator from trinomial $(x^2-x+1)$ to binomial $(x^3+1)$. – farruhota Nov 26 '18 at 12:42
• oh yess I understand, can u give more explanation on how the −x^2002 comes from ? – Aster Zen Nov 26 '18 at 12:45

You can also proceed artificially, since you already know the solution.

$$x^{2007}+1 = (x^3+1)\underbrace{\Big((x^3)^{668}+(x^3)^{667}+...+(x^3)^{2}+x^3+1\Big)}_{q(x)}$$

So we have $$x^{2007}+1 = (x^3+1)q(x) = (x^2-x+1)\underbrace{(x+1)q(x)}_{k(x)}$$

so $$x^{2007} = (x^2-x+1)k(x)-1$$ and thus the remainder is $$-1$$.

Hint  For motivation recall the $$\rm\color{#c00}{easy}$$ way to compute the parity of a decimal integer via the parity of its units digit, and also the two similar divisibility tests listed below

\begin{align} 2\mid 10\ \ \ \ \Rightarrow\ \ n\bmod 2\ \ \,&= \, {\overbrace{(n\bmod 10)}^{\large \text{units digit}}}\bmod 2\\[.2em] 25\mid 100\ \ \Rightarrow\ \ n\bmod 25\, &= \, (n\bmod 100)\bmod 25\\[.3em] 7\!\cdot\!13=10^2\!-\!10\!+\!1\mid 10^3\!+\!1\ \ \Rightarrow\ \ n\bmod 7\!\cdot\!13\, &= \, (n\bmod 1001)\bmod 7\!\cdot\!13\\[.4em] \text{similarly}\ \ \ x^2\!-\!x\!+\!1\mid x^3\!+1\Rightarrow f\bmod x^2\!-\!x\!+\!1\ &=\ \underbrace{(f\bmod x^3\!+1)}_{\Large\color{#c00}{ x^3\ \equiv -1}}\bmod x^2\!-\!x\!+\!1 \end{align}

It is $$\rm\color{#c00}{easy}$$ to compute $$f\bmod x^{\large 3}\!+1\,$$ since we can use $$\,\color{#c00}{x^{\large 3}\equiv -1}\,$$ to reduce mod $$\color{#c00}3\,$$ all expts on $$x$$

namely we have $$\ x^{\large k}\! = x^{\large r+3q}\!\equiv (-1)^{\large q} x^{\large r}\$$ where $$\,r = k\bmod 3\, \le\, 2,\$$ because

$$\bmod x^{\large 3}+1\!:\ \ \color{#c00}{x^{\large 3}\equiv -1}\,\Rightarrow\, x^{\large 3q+r}\equiv (\color{#c00}{x^{\large 3}})^{\large q}x^{\large r}\equiv (\color{#c00}{-1})^{\large q}x^{\large r}$$

Remark  Alternatively we can use $$\,\color{#c00}{x^{\large 6}\equiv 1}\,$$ to reduce the expts $$\!\bmod 6,\,$$ a technique often used when we know the order of some element (or any multiple of the order).

The same optimization works in general when there is a multiple $$nm$$ of the modulus $$m$$ where modular arithmetic is $$\rm\color{#c00}{easier}$$. First easy-reduce $$\,x\bmod nm\,$$ then reduce that $$\!\bmod m,\,$$ i.e.

$$x\bmod m\ =\ (x\bmod nm)\bmod m\qquad$$

\begin{align}\text{valid by}\qquad\qquad\quad\, x\,\ &=\,\ x\bmod nm\,+\, q\,nm \ \ \text{ by the division }\ x\div nm\\[.2em] \Rightarrow\ \ x\bmod m\ &=\, (x\bmod nm)\bmod m \end{align}

In congruences $$\ \bbox[5px,border:1px solid red]{x\equiv \bar x\pmod{\!nm}\,\Rightarrow\, x\equiv \bar x\pmod{\! n}}\,\$$ by $$\,\ m\mid nm\mid x-\bar x$$

i.e. congruences persist modulo divisors of the modulus. Above $$\,\bar x = x\bmod nm$$

See also this answer for a similar but more complex example, and see this answer for the above divisibility test for $$13$$ and the test for $$2^k$$ using the initial $$k$$ decimal digits.