How to use Chinese Remainder Theorem

Question

A cubic polynomial $f(x)=ax^3+bx^2+cx+d$ gives remainders $-3x+3$ and $4x-1$ when divided by $x^2+x+1$ and $x^2+2x-4$. Find the value of $a,b,c,d$.

I know it’s easy but i wanna use Chinese Remainder Theorem(and Euclidean Algorithm) to solve it. A hint or a detailed answer would be much appreciated

Answer 1

Not sure about the usage of the formulas, one obvious way is to write

$$ax^3+cx^2+cx+d$$

$$=(ax+e)(x^2+x+1)+(-3x+3)$$

$$=(ax+f)(x^2+2x-4)+(4x-1)$$

Compare the coefficients of the different exponents of $x$ to find the unknowns

As for example, comparing the constants,

$$d=e+3=-4f-1$$

Answer 2

EDIT: I just noticed my answer below doesn't meet OP's expectations, as I'm not explicitely using the Chinese theorem. I haven't read the question carefully enough...

---

Reduction of $f(x)$ modulo $x^2+x+1$ can be computed by successively replacing all instances of $x^2$ in $f$ by $-x-1$, until we obtain an expression of degree $<2$. The process reduces $f(x)$ to $a(-x-1)x +b(-x-1) +cx +d=-ax^2+(c-a-b)x+d-b$, which in turns gives $ -a(-x-1)+(c-a-b)x+d-b = (c-b)x+a+d-b$.

The same method with $x^2+2x-4$ tells us that $f(x)$ reduces to $(c-2b+8a)x-8a+d$.

These two reductions must be respectively $-3x+3$ and $4x-1$. By very definition of equality between polynomials (that is, we can identify the coefficients), it reduces to the following system with $4$ equations and $4$ unknowns, which I let your solve by yourself:
$$\left\{ \begin{array}{} -3&=c-b\\ 3&=a+d-b\\ 4&=c-2b+8a\\ -1&=-8a+d\\ \end{array} \right.$$

Answer 3

$$ \left( x^{2} + x + 1 \right) \left( \frac{ - x - 7 }{ 31 } \right) - \left( x^{2} + 2 x - 4 \right) \left( \frac{ - x - 6 }{ 31 } \right) = \left( -1 \right) $$

is all you need. Cleaning up, $$ (x+7) \left( x^{2} + x + 1 \right) - (x+6) \left( x^{2} + 2 x - 4 \right) = 31 $$

There is no guarantee of integer coefficients, even when both polynomials have integer coefficients. The units in $\mathbb Q[x]$ are nonzero rational constants.

Answer 4

Step 1: Using extended Euclidean algorithm, find $g(x)$ and $h(x)$ such that $$g(x)(x^2+2x-4)+h(x)(x^2+x+1)=1$$.

\begin{align} x^2+2x-4=x^2+x+1+(x-5)\implies& \begin{cases} q = 1\\ r=x-5\\ s=1\\ t=-1\end{cases}\\ x^2+x+1=(x+6)(x-5)+31\implies &\begin{cases} q = x+6\\ r=31\\ s=-(x+6)\\ t=1-(x+6)(-1)=x+7\end{cases}\\ x-5=\left(\frac{x-5}{31}\right)31\implies& \begin{cases} q = \frac{x-5}{31}\\ r=0\\ s= 1+\frac{x-5}{31}(x+6)=\frac{x^2+x+1}{31}\\ t=-1-\frac{x-5}{31}(x+7)=\frac{x^2+2x-4}{31}\end{cases} \end{align} Therefore, $g(x)=-\frac{x+6}{31}$ and $h(x)=\frac{x+7}{31}$.

Step 2: Using Chinese remainder theorem, \begin{align} f(x)&= (−3+3) + [(4−1)-(−3+3)]h(x)(x^2+x+1)\\&=(−3+3) +(7^3+3x^2+3x−4)\frac{(x+7)}{31}\\ &=\frac{7}{31}x^4+\frac{52}{31}x^3+\frac{24}{31}x^2-\frac{76}{31}x+\frac{65}{31} \end{align}