# Math Help - prove

1. ## prove

prove that if n and m are relatively prime, gcd(n,m)=1, then |U(n)|*|U(m)|=|U(nm)|

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