# polynomial division problem ( find the remainder)

How to find out what remainder will $\,(x-1)^{2013}\,$ have upon division by $\,x^2-2x+2\,?\;$

I've never solved anything like this before, so I have no ideas at all..

Hint: Upon division by $x^2 - 2x + \color{blue}{\bf{1}}$, there is no remainder: that is $$\frac{(x-1)^{2013}}{x^2 - 2x + 1} = \frac{(x - 1)^{2013}}{(x-1)^2} = (x - 1)^{2011}$$

Note: $\quad(x-1)^2 + 1 \equiv 0\pmod{x^2-2x+2}\;\implies\; (x-1)^2 \equiv -1 \pmod {x^2-2x+2}$

So what does this mean for

\begin{align} (x - 1)^{2013}\pmod{x^2 - 2x +2} &= (x-1)(x-1)^{2012}\pmod{x^2 - 2x +2} \\ &= (x-1)[(x-1)^2]^{2012/2}\pmod{x^2 - 2x +2}\\ &= (x-1)[(x-1)^2]^{1006}\pmod{x^2 - 2x + 1}\quad?\end{align}

• Ok, sorry. I removed my comment. – Julien Jan 27 '13 at 18:20

Hint $$(x-1)^{2013} = (x-1)((x-1)^2)^{1006}$$ but $(x-1)^2 \equiv -1 \pmod {x^2-2x+2}$

For even $n$, $(a^n-1)=(a+1)(a^{n-1}-a^{n-2}+\ldots+a-1)$.
For $a=(x-1)^2$ and $n=1006$:

$$(x-1)^{2012}-1=\\ \left[(x-1)^2+1\right]\left[(x-1)^{2010}-(x-1)^{2008}+(x-1)^{2006}-\ldots+(x-1)^2-1\right]\Longrightarrow \\ (x-1)^{2013}-(x-1)=\\\left[(x-1)^2+1\right]\left[(x-1)^{2011}-(x-1)^{2009}+(x-1)^{2007}-\ldots+(x-1)^3-(x-1)\right]\Longrightarrow \\ (x-1)^{2013}=\left(x^2-2x+2\right)(\cdots)+\color{red}{(x-1)}.$$

Hint $\$ The repeated squaring algorithm takes one step since $\rm\:(x\!-\!1)^2\equiv -1\pmod{x^2\!-2x+2)}$