Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
Thanks in advance.

share|cite|improve this question
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
up vote 3 down vote accepted

Yes, solve the four systems of congruences \begin{equation} \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} \end{equation}

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.