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!
 A: Hint Since $k=-X^2 \pmod{X^2+k}$, you have
$$P(X) \equiv X-X^2 \pmod{X^2+1} \\
P(X) \equiv X-X^2 \pmod{X^2+2} \\
P(X) \equiv X-X^2 \pmod{X^2+3} \\
P(X) \equiv X-X^2 \pmod{X^2+4} \\$$
A: Use the constructive proof of the Chinese remainder theorem.
The solution of the first two ones is $x-x^2$, obtained using Bézout's identity for $x^2+1$ and $x^2+2$.
It so happens that $x-x^2$ works for all other congruences: $x-x^2=(-1)(x^2+n)+(x+n)$.
A: 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$
A: Note that if $\ \color{#c00}{a_i - b_i} = c\ $ is constant (wrt $i)$ then below   reduces to CCRT = Constant-case CRT   $$\ \{\,f \equiv \color{#c00}{a_i}\!\!\!\pmod{\color{#c00}{b_i}}\,\}_{i=1}^k\! \iff \{\,f \equiv c\!\!\pmod{b_i}\,\}_{i=1}^k\iff f\equiv c\!\!\pmod{{\rm lcm}\{b_i\}}$$
since  $\  a_i \equiv b_i+c\equiv c\pmod{b_i}.\ $  This common optimization applies to your CRT system.
Remark $ $ Generally the solution will have form $\ f \equiv c \equiv a_i + d_i b_i  $ where the $d_i$ may depend on $i$ and need not be "small". But in human-constructed problems (exercises, contests) it if often worth testing small or constant $d_i,\,$ e.g. the obvious choice $\,d_i = -1\,$ in OP to eliminate dependence on $i$ in the constant terms by subtracting the modulus from the residue $\ x+i-(x^2+i) \equiv x-x^2.$ 
