Finding the remainder when a polynomial is divided by another polynomial. 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. :) 
 A: 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}$.

A: It can be done by (Lagrange) interpolation, but 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 $\, \underbrace{(x\!-\!1)}_{\large\color{#c00} g}-\underbrace{(x\!-\!2)}_{\large\color{#c00} h} = 1\Rightarrow \left[\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)}\right]$
