2
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ How did you come up with the solution for (i)? $1\cdot4 - 1\cdot(-3) = 1$? $\endgroup$ Commented Jan 19, 2018 at 13:05
  • $\begingroup$ 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. $\endgroup$
    – Bernard
    Commented Jan 19, 2018 at 13:36
  • $\begingroup$ You are right, but now I think there's a typo in your formula. Should it read $1 \cdot 4 - 1 \cdot 3$? $\endgroup$ Commented Jan 19, 2018 at 13:50
  • $\begingroup$ Yes. Sorry for the mistyping. I'll replace this comment, since it's too late to edit it. $\endgroup$
    – Bernard
    Commented Jan 19, 2018 at 13:56
  • $\begingroup$ No problem at all. Thanks for you help ^^ $\endgroup$ Commented Jan 19, 2018 at 21:14
1
$\begingroup$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .