# Combining results with Chinese remainder theorem - general case

suppose we have a congruence

$$ax^2+bx+c\equiv 0 \mod (p_1\cdot p_2)$$

being $p_1$ and $p_2$ primes - actually it should be possible to extend these considerations to an arbitrary number of primes - but let's keep it easy.

We know that the congruence has solution if and only if have solution the congruences:

$$ax^2+bx+c\equiv 0 \mod p_1$$

and

$$ax^2+bx+c\equiv 0 \mod p_2$$

Suppose the congruences have solutions:

$$x\equiv s_1 \mod p_1$$ $$x\equiv s_2 \mod p_1$$

and

$$x\equiv t_1 \mod p_2$$ $$x\equiv t_2 \mod p_2$$

I know I need to combine these results with CRT to find the (four, in this case) results modulo $p_1\cdot p_2$ of the original congruence. The problem is how?

I know that the CRT gives only one congruence, as a result, so my surmise is that I should combine the results as follows:

1. $x\equiv s_1 \mod p_1$ and $x\equiv t_1 \mod p_2$
2. $x\equiv s_2 \mod p_1$ and $x\equiv t_1 \mod p_2$
3. $x\equiv s_1 \mod p_1$ and $x\equiv t_2 \mod p_2$
4. $x\equiv s_2 \mod p_1$ and $x\equiv t_2 \mod p_2$

Is that correct?

-
Yes, that is correct. (We are assuming $p_1$ and $p_2$ are distinct.) – André Nicolas May 10 '14 at 18:48

Yes this is correct. The reasoning for why it is correct is just logic, and is as follows.

• All solutions to the first congruence are given by those integers $x$ such that $x \equiv s_1 \text{ or } s_2 \mod p_1$.

• All solutions to the second congruence are given by those integers $x$ such that $x \equiv t_1 \text{ or } t_2 \mod p_2$.

• Thus, an integer satisfies both congruences if and only if it is in both sets of integers, i.e. we need $(x \equiv s_1 \text{ or } s_2 \mod p_1)$ AND $(x \equiv t_1 \text{ or } t_2 \mod p_2)$. Which is equivalent to the four possibilities you list:

1. $x\equiv s_1 \mod p_1$ and $x\equiv t_1 \mod p_2$, OR
2. $x\equiv s_2 \mod p_1$ and $x\equiv t_1 \mod p_2$, OR
3. $x\equiv s_1 \mod p_1$ and $x\equiv t_2 \mod p_2$, OR
4. $x\equiv s_2 \mod p_1$ and $x\equiv t_2 \mod p_2$.

Then you solve each of the four cases with Chinese Remainder Theorem.

-