If every pair of congruence equations admits solutions, then the entire system admits solutions

Question

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;

$x\equiv(\gcd(c_2,c_3)x''+a')\mod{\operatorname{lcm(c_2',c_3')}}\quad(2)$

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

Answer 1

$\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})$.

Answer 2

Hint $\ $ By induction there is a solution $\,x = \color{#c00}b\,$ to the first $\,n\!-\!1\,$ congruences, i.e.

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

Combining this solution with the final $n$'th congruence it suffices to solve

$$\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, i.e.

$\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\!\!\overset{\color{darkorange}{\rm L}\!\!}\iff \:&\color{#0a0}{(c_n,c_i)}\mid b_n-b,\ \forall\, i < n,\ \rm true\ by\\[.1em] \bmod &\color{#0a0}{(c_n,c_i)}\!:\,{\underbrace{b_n\equiv\, \color{#c00}{b_i}}_{\!\!\!\large \rm hypothesis}\!\!\underbrace{\ \color{#c00}{\equiv b}\phantom{_.}}_{\large\ \ (\color{#c00}\#)\!\!\!}}\end{align}$

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

Remark $ $ Domains that satisfy the Chinese Remainder Theorem (CRT) solvability criterion, i.e. a system of congruences $\,x\equiv x_j\pmod{\!I_j}\,$ is solvable $\iff$ $\,x_j\equiv x_k \pmod{\! I_j + I_k}\,$ 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.