# Is there a better way to recombine these congruences?

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?

• 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).$$ – Servaes Apr 29 at 12:18

## 1 Answer

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.