So I had seen this problem in which the solution breaks an equation of the form $a \equiv b \pmod{n}$ into $3$ congruences of the form

$$ a \equiv b \pmod{p_1} $$ $$ a \equiv b \pmod{p_2} $$ $$ a \equiv b \pmod{p_3} $$ where $p_1, p_2$ and $p_3$ are relatively prime and $n = p_1 \cdot p_2 \cdot p_3$.

I was wondering whether I could do this:

If $N = q_1 \cdot q_2 \cdot q_3$ , $\; q_1, q_2, q_3$ are relatively prime and

$$ c_1 \equiv d_1 \pmod{q_1} $$ $$ c_2 \equiv d_2 \pmod{q_2} $$ $$ c_3 \equiv d_3 \pmod{q_3} $$

then whether I could recombine these $3$ congruences into one congruence relation.

I tried writing each of the 3 linear congruences in the form that Bézout's identity provides. But the only relation I got was $(c_1 - d_1) \cdot (c_2 - d_2) \cdot (c_3 - d_3) \equiv 0 \pmod{ q_1 \cdot q_2 \cdot q_3}$.

Is there a way to get it into something like $a \equiv b \pmod{n}$ form?

  • 1
    $\begingroup$ But it is already in this form; you have $b=0$ and $$a=(c_1 - d_1)(c_2 - d_2)(c_3 - d_3).$$ $\endgroup$ – Servaes Apr 29 '19 at 12:18

If $\ p_1,p_2,p_3\ $ are pairwise (!) coprime, then with those numbers, the product $\ n=p_1\cdot p_2\cdot p_3\ $ divides $\ a-b\ $ as well, giving $$a\equiv b\mod n$$ This is a consequence of the chinese remainder theorem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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