Combining results with Chinese remainder theorem - general case

Question

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?

Thanks in advance

Answer 1

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.