Exercise 2.3.20 (Existence of solutions of $x \equiv a_1 \pmod{m_1}, x \equiv a_2 \pmod {m_2}$.)

Proof.

a)

Let $S$ be the system of congruences $$\begin{array}{lll}\hfill \{\begin{array}{c}x\equiv a_1(\mathit{mod}{m}_1),\hfill \\ x\equiv a_2(\mathit{mod}{m}_2).\hfill \end{array}& & \hfill \end{array}$$

$\text{(⇒)}$

If $S$ has a solution $x\in \mathbb{Z}$, then $$g=m_1\wedge m_2\mid m_1,\text{ and }{m}_1\mid x-a_1,$$

thus $g\mid x-a_1$.

Similarly, $g\mid x-a_2$, therefore $g\mid (x-a_1)-(x-a_2)=a_2-a_1$, so

$$a_1-a_2\equiv 0(\mathit{mod}g).$$

$\text{(⇐)}$

Conversely, suppose that $a_1-a_2\equiv 0(\mathit{mod}g)$. Then there is some integer $k$ such that $a_2-a_1=\mathit{kg}$. Since $\frac{m_1}{g}\wedge \frac{m_2}{g}=1$, there are integers $\lambda ,\mu$ such that $$\lambda \frac{m_1}{g}-\mu \frac{m_2}{g}=k,$$

so

$$\lambda m_1-\mu m_2=\mathit{kg}=a_2-a_1.$$

Therefore $a_1+\lambda m_1=a_2+\mu m_2$.

Define $x=a_1+\lambda m_1$. Then $x=a_2+\mu m_2$, so $x$ satisfies

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

b)

Suppose now that the condition $a_1-a_2\equiv 0(\mathit{mod}g)$ is met, so that the system $S$ has an integer solution $x$.

If $y$ is another solution, then

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

therefore $m_1\mid y-x,m_2\mid y-x$. This implies $m_1\vee m_2\mid y-x$, thus

$$x\equiv y(\mathit{mod}{m}_1\vee m_2).$$

Conversely, if $x\equiv y(\mathit{mod}{m}_1\vee m_2)$, a fortiori $x\equiv y(\mathit{mod}{m}_1)$ and $x\equiv y(\mathit{mod}{m}_2)$. Therefore

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

so $y$ is a solution of $S$.

To conclude, if $x$ is a solution of $S$, then the solution of $S$ are

$$x+k(m_1\vee m_2),k\in \mathbb{Z}.$$