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

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 ?

Solution 1:

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.

Solution 2:

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