# How to combine congruences?

I have two congruences:

$$\text{(i) }p\equiv 1 \mod 3 \,\,\, \land \,\,\, p\equiv 1 \mod 4 \\ \text{(ii) }p\equiv 2 \mod 3 \,\,\, \land \,\,\, p\equiv 3 \mod 4$$

Is it possible to write these systems of congruences into a single congruence? To be clear: I don't want to combine (i) and (ii), but want to merge each statement into a single expression.

## 2 Answers

Yes. Since $$3$$ and $$4$$ are coprime, you need the Chinese remainder theorem for that. Namely

• (i) is equivalent to $$x\equiv 1\mod 12$$.
• (ii) requires the explicit formulation of the inverse isomorphism from $$\mathbf Z/3\mathbf Z\times \mathbf Z/4\mathbf Z \to \mathbf Z/12\mathbf Z$$. Start from a Bézout's relation between $$3$$ and $$4$$: $$4-3=1$$. The solution is given by $$x\equiv \color{red}2\cdot\color{lightgreen} 4-\color{lightgreen}3\cdot \color{red}3=-1\equiv 11\mod 12.$$

Added: you may write the general formula for the system of congruences modulo coprime numbers, given a Bézout's relation between $$a$$ and $$b$$: $$ua+vb=1\quad(u,v\in \mathbf Z)$$, $$\begin{cases} x\equiv \color{red}\alpha\mod \color{red}a \\ x\equiv \color{lightgreen}\beta\mod \color{lightgreen}b \end{cases} \iff x\equiv \color{lightgreen}\beta\,u\color{red}{a}+\color{red}\alpha\,v\color{lightgreen}{b}\mod ab.$$

• How did you come up with the solution for (i)? $1\cdot4 - 1\cdot(-3) = 1$? Commented Jan 19, 2018 at 13:05
• There's an error in your formula: it should be $1\cdot 1-1\cdot 3$. Any anyway since the r.h.s. side of the congruences is the same, the solution is obvious, precisely because we have an isomorphism. Commented Jan 19, 2018 at 13:36
• You are right, but now I think there's a typo in your formula. Should it read $1 \cdot 4 - 1 \cdot 3$? Commented Jan 19, 2018 at 13:50
• Yes. Sorry for the mistyping. I'll replace this comment, since it's too late to edit it. Commented Jan 19, 2018 at 13:56
• No problem at all. Thanks for you help ^^ Commented Jan 19, 2018 at 21:14

Since $\gcd(3,4) = 1$, by the Chinese Remainder Theorem, the solution is given by

1. $p \equiv 1 \pmod{12}$
2. $p \equiv 11 \pmod{12}$