# Finding the remainder when a polynomial is divided by another polynomial. [duplicate]

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?

-

## marked as duplicate by lhf, user91500, amWhy, Joe Johnson 126, 2mkgzJun 30 '14 at 16:06

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}$.
-
Oh, I see. Thanks a lot. :) –  EuclidAteMyBreakfast Jun 30 '14 at 10:29
You're welcome. –  Sami Ben Romdhane Jun 30 '14 at 10:29
@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. –  rah4927 Jun 30 '14 at 11:28
Wow, Sami, you've gotten a handful of $>10 \uparrow$'s! –  amWhy 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)}$

-