<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] 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} \\$$
</s>