<s>[INST] Chinese Remainder theorem polynomials Is there a program, small script, or easy method I can use to find the polynomial P(x) such that:
$P(x) = x+1$ $\pmod {x^2+1}$
$P(x) = x+2$ $\pmod {x^2+2}$
$P(x) = x+3$ $\pmod {x^2+3}$
$P(x) = x+4$ $\pmod {x^2+4}$
.........
This is easy to do with integers, but I can't get across this with polynomials. Thanks for help!
 [/INST] It didn't take too long to compute the following table of moduli.
\begin{array}{r|cccc}
   & x^2 + 1 & x^2 + 2 & x^2 + 3 & x^2 + 4 \\
\hline
\dfrac 16(x^2+2)(x^2+3)(x^2+4)  & 1 & 0 & 0 & 0 \\
-\dfrac 12(x^2+1)(x^2+3)(x^2+4) & 0 & 1 & 0 & 0 \\
\dfrac 12(x^2+1)(x^2+2)(x^2+4)  & 0 & 0 & 1 & 0 \\
-\dfrac 16(x^2+1)(x^2+2)(x^2+3) & 0 & 0 & 0 & 1 \\
\hline
\end{array}
It follows that
\begin{align}P(x) =
   & \dfrac 16(x^2+2)(x^2+3)(x^2+4)(x+1)- \\
   & \dfrac 12(x^2+1)(x^2+3)(x^2+4)(x+2)+ \\
   & \dfrac 12(x^2+1)(x^2+2)(x^2+4)(x+3)- \\
   & \dfrac 16(x^2+1)(x^2+2)(x^2+3)(x+4)
\end{align}
With the help of Wolfram alpha, this expands to $f(x) = x-x^2$
</s>