How to combine congruences?

Question

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.

Answer 1

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.$$

Answer 2

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}$