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$? 
 A: 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. 
A: 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.
A: 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$.
A: 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}.$$
A: 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.
