# Euler phi function

• Jan 21st 2009, 12:43 PM
asub1
Euler phi function
hi,

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

thanks
• Jan 21st 2009, 01:52 PM
ThePerfectHacker
Quote:

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)$.
• Jan 22nd 2009, 03:13 AM
asub1
Thank you very much!(Clapping)
• Jan 22nd 2009, 03:19 AM
asub1
Thank you very much again