4
$\begingroup$

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.

$\endgroup$
2
  • 8
    $\begingroup$ "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? $\endgroup$
    – blue
    Apr 28, 2014 at 5:03
  • $\begingroup$ @seaturtles That was the funniest comment I've read in a while... $\endgroup$
    – user142299
    Apr 28, 2014 at 6:08

3 Answers 3

19
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ Hey you stole my exact solution :) $\endgroup$
    – user142299
    Apr 28, 2014 at 4:13
  • $\begingroup$ @NotNotLogical Gotta be quick round here ;-) $\endgroup$
    – David
    Apr 28, 2014 at 4:13
  • $\begingroup$ got it....now putting x=2 and x=1 we can find a and b...thank you @ david.. $\endgroup$ Apr 28, 2014 at 4:16
  • $\begingroup$ 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... $\endgroup$
    – user142299
    Apr 28, 2014 at 4:21
  • 1
    $\begingroup$ 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? $\endgroup$
    – Chris
    Apr 28, 2014 at 12:49
10
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I think there will be problems if $r_1,\ldots,r_n$ are not all different, otherwise, great! +1 $\endgroup$
    – David
    Apr 28, 2014 at 4:34
  • $\begingroup$ @David Thank you, edited. $\endgroup$
    – user142299
    Apr 28, 2014 at 4:36
  • $\begingroup$ 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$. $\endgroup$
    – David
    Apr 28, 2014 at 4:46
  • $\begingroup$ @David Lol I was working on the edit above as you wrote that comment! Great minds think alike :) $\endgroup$
    – user142299
    Apr 28, 2014 at 4:54
  • $\begingroup$ @David This is interesting - it's sort of a hybrid between Taylor interpolating with derivatives and Discrete interpolating with points. $\endgroup$
    – user142299
    Apr 28, 2014 at 4:56
2
$\begingroup$

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

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