Exercise 2.3.23* (Solvability of the general system)

Proof.

$\text{(⇒)}$

Suppose that the integer $x$ satisfies the system $S$: $$x\equiv a_1(\mathit{mod}{m}_1),\dots ,x\equiv a_r(mod{m}_r).$$

Then for all $(i,j)$ such that $1\le i<j\le r$,

$$\{\begin{array}{c}x\equiv a_i(\mathit{mod}{m}_i),\hfill \\ x\equiv a_j(\mathit{mod}{m}_j).\hfill \end{array}$$

By Problem 20, $a_i\equiv a_j(\mathit{mod}{m}_i\wedge m_j).$

$\text{(⇐)}$

Suppose that $a_i\equiv a_j(\mathit{mod}{m}_i\wedge m_j)$ for all $(i,j)$ for which $1\le i<j\le r$. We prove by induction on $r\ge 2$ that the system $S$ has a solution.

Let ${(a_i)}_{i\in \mathbb{N}},{(m_i)}_{i\in \mathbb{N}}$ be any sequences of integers, and define

$$\begin{array}{llll}\hfill 𝒫(r)⟺(\forall <!--\; FUNCTION\; APPLICATION\; -->(i,j)\in {[[1,r]]}^2,& 1\le i<j\le r\Rightarrow a_i\equiv a_j(\mathit{mod}{m}_i\wedge m_j))& \hfill & \\ \hfill & \Rightarrow \exists <!--\; FUNCTION\; APPLICATION\; -->x\in \mathbb{Z},\forall <!--\; FUNCTION\; APPLICATION\; -->i\in [[1,r]],x\equiv a_i(\mathit{mod}{m}_i).& \hfill & \end{array}$$

• If $r=2$, since $a_1\equiv a_2(\mathit{mod}{m}_1\wedge m_1)$, by Problem 20, there exists a solution $x$ of the system

  $$\{\begin{array}{c}x\equiv a_1(\mathit{mod}{m}_1),\hfill \\ x\equiv a_2(\mathit{mod}{m}_2).\hfill \end{array}$$

  so $𝒫(2)$ is true.

• Suppose that $𝒫(r)$ is true, and assume $a_i\equiv a_j(\mathit{mod}{m}_i\wedge m_j)$ for all $(i,j)$ such that $1\le i<j\le r+1$. Using the induction hypothesis, we know that there is some integer $x_0$ such that

  $$x_0\equiv a_1(\mathit{mod}{m}_1),\dots ,x_0\equiv a_r(mod{m}_r).$$

  Since $m_i\wedge m_{r+1}\mid m_i$,

  $$\begin{array}{llll}\hfill & x_0\equiv a_1\equiv a_{r+1}(\mathit{mod}{m}_1\wedge m_{r+1}),& \hfill & \\ \hfill & \dots & \hfill & \\ \hfill & x_0\equiv a_r\equiv a_{r+1}(\mathit{mod}{m}_r\wedge m_{r+1}).& \hfill & \end{array}$$

  Therefore

  $$m_1\wedge m_{r+1}\mid x_0-a_{r+1},\dots ,m_r\wedge m_{r+1}\mid x_0-a_{r+1},$$

  and this implies

  $$(m_1\wedge m_{r+1})\vee \cdots \vee (m_r\wedge m_{r+1})\mid x_0-a_{r+1}.$$

  Moreover,

  $$(m_1\wedge m_{r+1})\vee \cdots \vee (m_r\wedge m_{r+1})=(m_1\vee m_2\vee \cdots \vee m_r)\wedge m_{r+1}:$$

  we use the distributivity law

  $$(a\vee b)\wedge c=(a\wedge c)\vee (b\wedge c),$$

  which is proved by comparing the exposant of a prime $p$ in both members, using

  $$\min <!--\; FUNCTION\; APPLICATION\; -->(\max <!--\; FUNCTION\; APPLICATION\; -->(\alpha ,\beta ),\gamma )=\max <!--\; FUNCTION\; APPLICATION\; -->(\min <!--\; FUNCTION\; APPLICATION\; -->(\alpha ,\gamma ),\min <!--\; FUNCTION\; APPLICATION\; -->(\beta ,\gamma )).$$

  We obtain

  $$(m_1\vee m_2\vee \cdots \vee m_r)\wedge m_{r+1}\mid x_0-a_{r+1}.$$

  Therefore, Problem 20 shows that there is some integer $x$ such that

  $$\{\begin{array}{cc}x\equiv x_0\hfill & (\mathit{mod}{m}_1\vee \cdots \vee m_r),\hfill \\ x\equiv a_{r+1}\hfill & (\mathit{mod}{m}_{r+1}).\hfill \end{array}$$

  Since $m_i\mid m_1\vee \cdots \vee m_r$, $x\equiv x_0\equiv a_i(\mathit{mod}{m}_i)$ for $i=1,\dots ,r$, and $x\equiv a_{r+1}(\mathit{mod}{m}_{r+1})$, so

  $$x\equiv a_i(\mathit{mod}{m}_i),i=1,\dots ,r,r+1,$$

  and the induction is done.

To conclude, there is a simultaneous solution of the system $S$ if and only if $a_i\equiv a_j(\mathit{mod}{m}_i\wedge m_j)$ for all $(i,j)$ such that $1\le i<j\le r$.