# Math Help - Euler phi function

1. ## Euler phi function

hi,

I need help
let $gcd(n, m) = 1$ prove that $\phi(nm)=\phi(n)\phi(m)$

thanks

2. Originally Posted by asub1
hi,

I need help
let $gcd(n, m) = 1$ prove that $\phi(nm)=\phi(n)\phi(m)$

thanks
Define a function, $\phi : \mathbb{Z}_{nm}^{\times} \to \mathbb{Z}_n^{\times}\times \mathbb{Z}_m^{\times}$ by $\phi ([x]_{nm}) = ([x]_n,[x]_m)$.
Now argue that this mapping is one-to-one and onto by the Chinese remainder theorem.
And so it follows that $|\mathbb{Z}_{nm}^{\times}| = |\mathbb{Z}_n^{\times}| \times |\mathbb{Z}_m^{\times} | \implies \phi(nm) = \phi(n)\phi(m)$.

3. Thank you very much!

4. Thank you very much again