Take the 2-minute tour ×
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.

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

share|improve this question
2  
Yes, that is correct. (We are assuming $p_1$ and $p_2$ are distinct.) –  André Nicolas May 10 at 18:48

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

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.