A cubic polynomial gives remainders $(13x-2)$ and $(-1-7x)$ when divide by
$x^2-x-3$ and $x^2-2x+5$ respectively. Find the polynomial.
I have written this as:
$P(x)=(x^2-x-3)Q(x)+(13x-2)$
$P(x)=(x^2-2x+5)G(x)+(-1-7x)$
and
$P(x)=ax^3+bx^2+cx+d$
The first method I thought about is factoring $(x^2-x-3)$ and $(x^2-2x+5)$ so that I could find roots and thereby $P(root)$ would equal the reminder for the given value of root. As the two quadratic equations would give four roots i.e. four values I can substitute, I would be able to calculate all the four constant $a$, $b$, $c$ and $d$. However, the first polynomial has very ugly roots and the second one has no real roots so I guess I should find another way. What do you suggest?
Best Answer
Using the Extended Euclidean Algorithm as implemented in this answer, we get $$ \begin{array}{r} &&1&x+6&(x-8)/53\\\hline 1&0&1&-x-6&(x^2-2x+5)/53\\ 0&1&-1&x+7&(-x^2+x+3)/53\\ x^2-x-3&x^2-2x+5&x-8&53&0\\ \end{array} $$ That is, $$ (x+7)(x^2-2x+5)-(x+6)(x^2-x-3)=53\tag{1} $$ We can now use the Chinese Remainder Theorem. $(1)$ tells us that $$ \frac{x+7}{53}\,(x^2-2x+5)\equiv \left\{\begin{array}{} 0&\pmod{x^2-2x+5}\\ 1&\pmod{x^2-x-3} \end{array}\right.\tag{2} $$ $$ -\frac{x+6}{53}\,(x^2-x-3)\equiv \left\{\begin{array}{} 1&\pmod{x^2-2x+5}\\ 0&\pmod{x^2-x-3} \end{array}\right.\tag{3} $$ Add $13x-2$ times $(2)$ and $-1-7x$ times $(3)$ to get $$ \frac1{53}\left(20x^4+99x^3-185x^2+338x-88\right)\tag{4} $$ taking the remainder of $(4)$ mod $(x^2-x-3)(x^2-2x+5)$ gives $$ 3x^3-5x^2+6x+4\tag{5} $$