# Give the remainder of $x^{100}$ divided by $(x-2)(x-1)$.

What will be the remainder obtained when the polynomial $x^{100}$ is divided by the polynomial $(x-2)(x-1)$.

I used remainder theorem but it had no impact in the solution.

-
"I used remainder theorem but it had no impact in the solution." What does this mean? I used the remainder theorem and got the solution straight away; what did you do? –  blue Apr 28 '14 at 5:03
@seaturtles That was the funniest comment I've read in a while... –  NotNotLogical Apr 28 '14 at 6:08

Hint. The remainder will be a linear polynomial $ax+b$; you need to find $a$ and $b$. By division we have $$x^{100}=(x-2)(x-1)q(x)+ax+b\ .$$ Now substitute two convenient values of $x$ in order to find two equations involving $a$ and $b$.

-
Hey you stole my exact solution :) –  NotNotLogical Apr 28 '14 at 4:13
@NotNotLogical Gotta be quick round here ;-) –  David Apr 28 '14 at 4:13
got it....now putting x=2 and x=1 we can find a and b...thank you @ david.. –  soumajit das Apr 28 '14 at 4:16
It's interesting because I thought of the same solution, but I've never come across an exercise remotely like this... I wonder if it could be generalized in any way... –  NotNotLogical Apr 28 '14 at 4:21
Out of interest what is the proof that the remainder will be of the form ax+b? It seems like there should be a simple answer but I can't quite see it (happy to ask as a separate question if its not a comment length answer). Oh - or is it just that it must be a smaller order polynomial than what you are dividing by? –  Chris Apr 28 '14 at 12:49

Just for fun, I will generalize the thread provided in @David's excellent answer.

We divide $p(x)$ by the quadratic $(x-a)(x-b)$ to get $$p(x)=(x-a)(x-b)Q(x)+(mx+n)$$ for some linear remainder. Plugging in $a$ and $b$ respectively gives \begin{align}p(a)=am+n \\ p(b)=bm+n \end{align} Solving then for the parameters, we have \begin{align} m=&\frac{p(b)-p(a)}{b-a} \\ n=&\frac{b\,p(a)-a\,p(b)}{b-a}\end{align} In general, it seems that the remainder of a polynomial $p$ by an $n$th degree divisor $d(x)=(x-r_1)\cdots (x-r_n)$ with $r_i\ne r_j,\;i\ne j$, is the interpolating polynomial of degree $n-1$ which goes through the $n$ points $$\Big(r_1,p(r_1)\Big),\,\dots\,,\Big(r_n,p(r_n)\Big)$$

And to generalize even further, suppose that $d(x)=(x-r_1)^{n_1}\cdots (x-r_k)^{n_k}$ is a divisor of degree $n=n_1+\cdots n_k$. Then $$p(x)=(x-r_1)^{n_1}\cdots (x-r_k)^{n_k}\,Q(x)+R(x)$$ This will give the system of equations \begin{align}R(r_1)&=&p(r_1) \\ R'(r_1)&=&p'(r_1) \\ &\vdots& \\ R^{(n_1-1)}(r_1)&=&p^{(n_1-1)}(r_1) \\ \\ &\vdots& \\ \\ R^{(n_k-1)}(r_k)&=&p^{(n_k-1)}(r_k)\end{align} which is $n$ variables in $n$ equations.

-
I think there will be problems if $r_1,\ldots,r_n$ are not all different, otherwise, great! +1 –  David Apr 28 '14 at 4:34
@David Thank you, edited. –  NotNotLogical Apr 28 '14 at 4:36
You could probably still manage the problem with a bit more work. Example: find the remainder when $x^{100}$ is divided by $(x-2)^2(x-1)$. Solution: writing the division and differentiating,$$x^{100}=(x-2)^2(x-1)q(x)+ax^2+bx+c\ ,\quad 100x^{99}=(x-2)(\cdots)+2ax+b\ ;$$now substitute $x=2$ and $x=1$. –  David Apr 28 '14 at 4:46
@David Lol I was working on the edit above as you wrote that comment! Great minds think alike :) –  NotNotLogical Apr 28 '14 at 4:54
@David This is interesting - it's sort of a hybrid between Taylor interpolating with derivatives and Discrete interpolating with points. –  NotNotLogical Apr 28 '14 at 4:56

By the Chinese remainder theorem for the polynomial ring $K[x]$ (where $K$ is your unspecified base field, probably the real or complex numbers), and the obvious fact that the polynomials $x-1$ and $x-2$ are relatively prime, the quotient ring $K[x]/((x-1)(x-2))$ is isomorphic to the product ring $K[x]/(x-1)\times K[x]/(x-2)$, with the two components of the isomorphism to the product being given by further reducing modulo $x-1$ respectively modulo $x-2$ (the input was already reduced modulo $(x-1)(x-2)$, whence the "further").

Now those further reductions applied to the class of $x$ gives $1$ respectively $2$, so $x$ corresponds to the element $(1,2)$ of the product ring. Then $x^{100}$ is immediately computed in the product ring as $(1,2^{100})$. It remains to realise that value as the isomorphic image of the class of a single polynomial of degree${}<2$, which polynomial is then the remainder of $x^{100}$ after division by $(x-1)(x-2)$, as this is the preferred representative of the class of $x^{100}$ in $K[x]/((x-1)(x-2))$. The image of the class of $ax+b$ in the product is $(a+b,2a+b)$ so it suffices to sove the system \begin{aligned} a+b &= 1 \\ a+2b &= 2^{100} \end{aligned} which gives $b=2^{100}-1$ and $a=2-2^{100}$.

-