# Polynomial equations over $\mathbb{Z}_m$ where m is not a power of a prime

When I have a polynomial equation over $\mathbb{Z}_m$ and $m=p_1^{l_1}\cdot \ldots \cdot p_k^{l_k}$
First for every $\,p_i^{l_i}\,$ I solve using Hensel Lifting $\,f(x)\equiv 0\,(mod\,p_i^{l_i})$
For example, results I get look like:

$\begin{array}{l} f(x)=x^2+5x+24\equiv 0\,(mod\,36)\\ x \equiv 0,3 \,(mod\, 2^2)\\ x \equiv 6,7 \,(mod\, 3^2) \end{array}$

Now what? Do I use Chinese Remainder Theorem? For which of the results? (0,6) and (3,7) separately?

-
You suggest using the Chinese Remainder Theorem and this seems to be a good idea. Have you already tried this to see what happens? There are four possible combinations out there, which can be `lifted' to possible solutions mod 36. Just plug them into your $f$ and see what happens - they should all be solutions to $f(x)=0$. –  HSN Jan 29 '13 at 14:37
Using the Chinese Remainder Theorem only for 0 and 3 mod 2^2 makes non sense and so does 6 and 7 mod 3^2. I feel confused how am I supposed to "combine" these. –  The-Q Jan 29 '13 at 14:41
No, but you can combine each of the results mod 4 with each of the results mod 9, as @Anderas Caranti explicitly states below. You can't use the chinese remainder theorem on different numbers mod 4, since 4 and 4 are not relatively prime. –  HSN Jan 29 '13 at 15:13

Yes, solve the four systems of congruences $$\begin{cases}x \equiv 0 \pmod{4}\\x \equiv 6\pmod{9}\end{cases} \quad \begin{cases}x \equiv 0 \pmod{4}\\x \equiv 7\pmod{9}\end{cases} \quad \begin{cases}x \equiv 3 \pmod{4}\\x \equiv 6\pmod{9}\end{cases} \quad \begin{cases}x \equiv 3 \pmod{4}\\x \equiv 7\pmod{9}\end{cases}$$

-