Exercise 2.3.24* (Complete system of residues modulo $m_1m_2\cdots m_r$.)

Proof. Consider the map

We show first that $\phi$ is injective(one-to-one).

Suppose that $\phi (c_1,\dots ,c_r)=\phi (d_1,\dots ,d_r)$, where $(c_1,\dots ,c_r),(d_1,\dots ,d_r)$ are in $𝒞(m_1)\times \cdots \times 𝒞(m_r)$. Then

If we write $e_i=c_i-d_i$ for $i=1,\dots ,r$, we obtain

so

for some integer $\lambda$. It remains to prove by induction that $e_i=0$ for $i=1,\dots ,r$.

• First $m_1\mid \lambda m_1\cdots m_r-(e_2{m}_1+e_3{m}_1{m}_2+\cdots +e_r{m}_1{m}_2\cdots m_{r-1})=e_1$, thus $m_1\mid e_1=c_1-d_1$, so

  $$c_1\equiv d_1(\mathit{mod}{m}_1).$$

  Moreover $c_1,d_1$ are elements of the same complete system $𝒞(m_1)$ of residues modulo $m_1$, and are congruent modulo $m_1$, therefore $c_1=d_1$, so $e_1=0$.

• Suppose now that $e_1=e_2=\cdots =e_k=0$, where $k<r$. Then

  $$e_{k+1}{m}_1{m}_2\cdots m_k+\cdots +e_r{m}_1{m}_2\cdots m_r=\lambda m_1{m}_2\cdots m_r.$$

  Simplifying by $m_1{m}_2\cdots m_k$, we obtain

  $$e_{k+1}+e_{k+2}{m}_{k+1}+\cdots +e_r{m}_{k+1}\cdots m_{r-1}=\lambda m_{k+1}\cdots m_r.$$

  Then $m_{k+1}\mid \lambda m_{k+1}\cdots m_r-(e_{k+2}{m}_{k+1}+\cdots +e_r{m}_{k+1}\cdots m_{r-1})=e_{k+1}$, thus $m_{k+1}\mid e_{k+1}=c_{k+1}-d_{k+1}$, so

  $$c_{k+1}\equiv d_{k+1}(\mathit{mod}{m}_{k+1}).$$

  Moreover $c_{k+1},d_{k+1}$ are elements of the same complete system $𝒞(m_{k+1})$ of residues modulo $m_{k+1}$, and are congruent modulo $m_{k+1}$, therefore $c_{k+1}=d_{k+1}$, so $e_{k+1}=0$.

• We can conclude this induction: $e_1=e_2=\cdots =e_r=0$ thus $(c_1,\dots ,c_r)=(d_1,\dots ,d_r)$. This proves that $\phi$ is injective.

Then $\phi :𝒞(m_1)\times \cdots \times 𝒞(m_r)\to \mathbb{Z}∕\mathit{m\mathbb{Z}}$ is injective, and

This proves that $\phi$ is also surjective (onto), thus $\phi$ is a bijection.

Write $𝒞$ for the set of numbers $c_1+c_2{m}_1,+c_3{m}_1{m}_2+\cdots +c_r{m}_1{m}_2\cdots m_{r-1},$ where $c_j\in 𝒞(m_j)$ for $j=1,\dots ,r$.

Since, $\phi$ is bijective, for any integer $n$, there is a unique element $c=c_1+c_2{m}_1,+c_3{m}_1{m}_2+\cdots +c_r{m}_1{m}_2\cdots m_{r-1}\in 𝒞$ such that

This shows that $𝒞$ is a complete system of residues modulo $m=m_1{m}_2\cdots m_r$. □