Find the remainder when $x^{100}$ is divided by $x^2 - 3x + 2$.

I tried solving it by first calculating the zeroes of $x^2 - 3x + 2$, which came out to be 1 and 2.

So then, using the Remainder Theorem, I put both their values, and so the remainder came out to be $1 + 2^{100}$.

But the correct answer is $(2^{100} - 1)x + (2 - 2^{100})$.

Can you please explain the exact process to reach the solution?

Thanks in advance. :)


marked as duplicate by lhf, user91500, Namaste, Joe Johnson 126, user147263 Jun 30 '14 at 16:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


We write the Euclidean division:

$$x^{100}=(x^2-3x+2)Q(x)+ax+b$$ and notice that $1$ and $2$ are roots of $x^2-3x+1$ so

  • let $x=1$ we get $1=a+b$
  • let $x=2$ we get $2^{100}=2a+b$ so we find $a=2^{100}-1$ and $b=2-2^{100}$.
  • $\begingroup$ Oh, I see. Thanks a lot. :) $\endgroup$ – EuclidAteMyBreakfast Jun 30 '14 at 10:29
  • $\begingroup$ You're welcome. $\endgroup$ – user63181 Jun 30 '14 at 10:29
  • $\begingroup$ @Euclidatemybreakfast,a very similar problem that may have motivated this solution is as follows:$f(x)$ is a polynomial which leaves a remainder of 1 upon division by (x-1) and a remainder of 2 upon division by (x-2).What is the remainder when the polynomial is divided by (x-1)(x-2)?Your problem is exactly the same problem in disguise. $\endgroup$ – rah4927 Jun 30 '14 at 11:28
  • $\begingroup$ Wow, Sami, you've gotten a handful of $>10 \uparrow$'s! $\endgroup$ – Namaste Jul 1 '14 at 12:14

Though it can be done by (Lagrange) interpolation, it's just as simple (and much more powerful) to use the Chinese Remainder Theorem (CRT), which is $\color{#c00}{\rm very\ easy}$ when the $\color{#c00}{\rm Bezout}$ identity is known

By CRT, $ $ if $\ \color{#c00}{j g} + \color{#c00}{k h} = 1\,$ then $\ \begin{eqnarray}f\equiv a\!\!\!\pmod g\\f\equiv b\!\!\!\pmod h\end{eqnarray}$ $\!\iff$ $\begin{eqnarray} f&\equiv&\ a\,\color{#c00}{kh}\, +\, b\,\color{#c00}{jg}&&({\rm mod}\ {gh})\\ &\equiv& a+(b\!-\!a)\color{#c00}{jg}&&({\rm mod}\ gh)\end{eqnarray}$

So, by $\ \underbrace{(x\!-\!1)}_{\large g}-\underbrace{(x\!-\!2)}_{\large h} = 1\,$ then $\ \begin{eqnarray} f(1) = a\\ f(2) = b\end{eqnarray}\ \iff\ f\equiv a+(b\!-\!a)\color{#c00}{(x\!-\!1)} \pmod{(x\!-\!1)(x\!-\!2)}$


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