Let a system of three linear congruence equations in integers be given;

\begin{cases}x\equiv b_1\mod c_1\\ x\equiv b_2\mod c_2\\ x\equiv b_3\mod c_3\\ \end{cases} with $c_1,c_2,c_3\in\mathbb Z_{+}$. Show that, if every pair of congruence equations admits solutions, then the entire system admits solutions.

Now, if every pairs admits solutions, then for example $b_1\equiv b_2\equiv a\mod \gcd(c_1,c_2)$ for some $a$ then;

$x-a\equiv b_1-a\mod c_1$

$x-a\equiv b_2-a\mod c_2$

replacing $x$ by $x':=\frac{x-y}{\gcd(c_1,c_2)}$, we obtain:

$x'\equiv b_1'\mod c_1'$

$x'\equiv b_2'\mod c_2'$

and since $\gcd(c_1,c_2)=1$ by Chinese Remainder Theorem we have a unique solution $\mod{c_1'c_2'}$, so $x\equiv (\gcd(c_1,c_2)x'+a)\mod{\operatorname{lcm(c_1',c_2')}}\quad(1)$

We can do it with another pair (take $2$nd and $3$rd, since we know that such a pair admits solutions;


Now how can I show that for the pair $(1)$ and $(2)$ also solutions exist ?


$\newcommand{\lcm}{\mathrm{lcm}}$All pairs of equations have a solution iff $\gcd(c_{i}, c_{j}) \mid b_{i} - b_{j}$ for all $i, j$. So assume this holds.

Let $b$ be a solution of the first two congruences, so that $b \equiv b_{1} \pmod{c_{1}}$ and $b \equiv b_{2} \pmod{c_{2}}$. The system of three equations thus reduces to a system of two equations: $$ \begin{cases} x \equiv b \pmod{\lcm(c_{1}, c_{2})}\\ x \equiv b_{3} \pmod {c_{3}} \end{cases} $$ This has a solution iff $b - b_{3}$ is divisible by $$ \gcd(\lcm(c_{1}, c_{2}), c_{3}) = \lcm(\gcd(c_{1}, c_{3}), \gcd(c_{2}, c_{3})).. $$ It is enough to show that $\gcd(c_{1}, c_{3})$ divides $b - b_{3}$, the argument for $\gcd(c_{2}, c_{3})$ being exactly the same. Now $\gcd(c_{1}, c_{3})$ divides $b_{1} - b_{3}$, and $b \equiv b_{1} \pmod{c_{1}}$, so that $\gcd(c_{1}, c_{3})$ divides $b - b_{1}$, and thus $\gcd(c_{1}, c_{3})$ divides $b - b_{3} = (b - b_{1}) + (b_{1} - b_{3})$.

| cite | improve this answer | |
  • $\begingroup$ Thanks @BillDubuque, but unless I am confused (which might well be), you appear to be dealing with the case when you fix the $c_{i}$, and assume pairwise solvability for any choice of the $b_{i}$ (so I think you are assuming the $c_{i}$ to be pairwise coprime). I am dealing the case where you have pairwise solvability for a particular choice of the $b_{i}$ and $c_{i}$. $\endgroup$ – Andreas Caranti Mar 9 '15 at 7:33
  • $\begingroup$ @BillDubuque, still, thanks for the very nice argument in your answer, which I will definitely reuse (with proper credit) in my own lectures. $\endgroup$ – Andreas Caranti Mar 9 '15 at 16:00

Hint $\ $ Suppose for induction there is a solution $\,x = b\,$ to the first $\,n\!-\!1\,$ congruences, i.e.

$$\qquad\ b\equiv b_i\!\!\!\pmod{c_i},\,\ i=1,\ldots n-1\qquad\ \ (\color{#c00}\#)$$

Combining the solution with the final congruence we obtain the system

$$\begin{align} &x \equiv b\! \pmod {\!c},\,\ \ c = {\rm lcm}(c_1,\ldots c_{n-1})\\ &x\equiv b_n\!\!\!\! \pmod{\!c_n}\end{align}$$

That's solvable $\!\iff (c_n,c)\mid b_n-b,\ $ which is true by gcd distributes over lcm so we have

$\qquad\ \,\color{#90f}{(c_n,c)} = (c_n,{\rm lcm}(c_1,\ldots c_{n-1}) = {\rm lcm}(\color{#0a0}{(c_n,c_1),\ldots,(c_n,c_{n-1})}) =: \ell $

$\begin{align}{\rm thus}\ \ \color{#90f}{(c_n,c)}\mid b_n-b\! \iff \ell\mid b_n-b\!\iff &\color{#0a0}{(c_n,c_i)}\mid b_n-b\ \ \,\forall\ i \le n\!-\!1,\ \rm true\ by\\[.2em] \bmod &\color{#0a0}{(c_n,c_i)}\!:\,{\underbrace{b_n\equiv\, b_i}_{\!\!\!\!\!\!\!\!\!\large \rm hypothesis}\!\!\!\!\underbrace{\phantom{b_i}\equiv b}_{\large\ \ (\color{#c00}\#)}}\end{align}$

where we used $\ {\rm lcm}(d_1,\ldots,d_k)\mid a\iff d_1,\ldots,d_k\mid a,\,$ the lcm Universal Property.

Remark $\ $ Domains satsifying CRT = Chinese Remainder Theorem are known as Prüfer domains. They are non-Noetherian generalizations of Dedekind domains. Their ubiquity stems from a remarkable confluence of interesting characterizations. See this answer for a couple dozen characterizatons.

| cite | improve this answer | |

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.