Lemma 1

If $a_1,a_2,...a_l$ are all relatively prime to m, then so is $a_1a_2a_3...a_l$.

Proof: $$\bar a_1 \bar a_2 \bar a_3 ... \bar a_l = \overline{a_1a_2a_3...a_l}$$ So $(a_1a_2a_3...a_l,m)=1$

Lemma 2

If $a_1,a_2,a_3,...a_l$ divides $n$ and $(a_i,a_j)=1$. Then $a_1a_2a_3...a_l$ divides $n$.

Proof:

For $l=1$, $a_1|n$.

Suppose that $a_1,a_2,...a_{l-1}$ divides $n$ and $(a_i,a_j)=1$. Then $a_1a_2...a_{t-1}$ divides $n$.

For $a_l$ relatively prime to all $a_1,a_2,...a_{l-1}$. $$pa_l+qa_1a_2...a_{l-1}=1$$ Obviously left side divides n.

Chinese Remainder Theorem

Suppose $m=m_1m_2m_3...m_t$ and that $(m_i,m_j)=1$.

Consider system: $$x=b_1(m_1),x=b_2(m_2),...,x=b_t(m_t)$$ This system always has solutions and any two solutions differ by a multiple of m.

Proof:

Let $n_i=m/m_i$, we already know $(m_i,n_i)=1$. That is $r_im_i+s_in_i=1$.

So we have $s_in_i \equiv 1 (m_i)$ and then $b_is_in_i \equiv b_i (m_i)$.

That indicate $x_0=\sum{b_is_in_i}$ is one of the solutions.

Suppose another solution $x_1 - x_0 \equiv 0 (m_i)$, $x_1$ is another solution. We have all $m_i|(x_1-x_0)$. So other solutions differ by $m$.

Isomorphism

Define

For rings $R_1,R_2,R_3,...,R_n$. Define the direct sum $R_1\bigoplus R_2 \bigoplus R_3...\bigoplus R_n= S =\{r_1 ,r_2,r_3,...r_n\}=\{r_i\}$. The addition is $\{r_i\}+\{r'_i\}={r_i+r'_i}$. The multiplication is $\{r_i\}\cdot\{r'_i\}={r_ir'_i}$. The zero is $\{0\}$ and identity is $\{1\}$. For $u\in S$ is a unit iff there is a $v \in S$ such that $uv=1$. That is ${u_iv_i}={1}$. Then we can consider a group of units $\prod U(R_i)$

Proposition 1

If $S = R_1\bigoplus R_2 \bigoplus R_3...\bigoplus R_n$, then $U(S)=U(R_1)U(R_2)...U(R_n)$.

Assume $m_1,m_2,...,m_t$ are all relatively prime. $\psi_i$ is the homomorphism from $\Z$ to $\Z/m_i\Z$. $$\psi(n) = \{\psi_1(n),\psi_2(n),...,\psi_t(n)\}$$ By CRT, there always exist a n that $\psi_i(n)=\bar b_i$ which is $n \equiv b_i(m_i)$. So $\psi$ is onto.

So the kernel is $ker(\psi_i) = m_i\Z$.

Therefore, we shown that $\psi$ allows isomorphism between $\Z/m\Z$ and $\bigoplus_{i=1}^{t}\Z/m_i\Z$.

By definition, a unit in $\Z/m\Z$ will be relatively prime with any $m_i$. And let $x_i$ be the unit of $\Z/m_i\Z$ we get $x = \{x_1,x_2,...,x_t\}$. $$U(\Z/m\Z) \cong U(\Z/m_1\Z) \times U(\Z/m_2\Z) \times U(\Z/m_3\Z) ... U(\Z/m_t\Z)$$ From the isomorphism, we can see the order of left side is $\phi(m)$ and the order of right side is $\prod\phi(m_i)$.

Let $m=\prod_i p_i^{a_i}$, we have $\phi(m)=\prod_i\phi(p_i^{a_i})$.

Considering $p^a$ is relatively prime to any number except some multiple of $p$, so there are $p^{a-1}$ number are multiple of $p$. That is $\phi(p^a)=p^a-p^{a-1} = p^a( 1- 1/p)$.

Therefore $$\phi(m) = m \prod_i (1-1/p_i)$$ In the end, we have two isomorphism: $$\Z/m\Z \cong \bigoplus_{i=1}^t \Z/p_i^{a_i}\Z$$

$$U(Z/m\Z) \cong \prod_{i=1}^t U(\Z/p_i^{a_i}\Z)$$