prove that if n and m are relatively prime, gcd(n,m)=1, then |U(n)|*|U(m)|=|U(nm)|
Define $\displaystyle \phi: \mathbb{Z}_{nm}^{\times}\to \mathbb{Z}_n^{\times} \times \mathbb{Z}_m^{\times}$ by $\displaystyle \phi( [x]_{nm}) = ( [x]_n, [x]_m)$.
Show this is well-defined.
Now prove this is a bijection by using Chinese remainder theorem.