4
$\begingroup$

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..

Thanks in advance!

$\endgroup$
7
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ Ok, sorry. I removed my comment. $\endgroup$ – Julien Jan 27 '13 at 18:20
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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)}. $$

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.